最近整理旧blog的时候一直在想：要不要带上原文链接。现在决定还是加在文章最后吧，既然是自己写的(尽管很水)，那么就留着对比一下吧，看看整理后的文章有多少提高。

这次的也是《数据结构基础(C语言版)(第2版)》(Fundamentals of Data Structures in C, 2nd)的一个练习题：给定n个布尔变量,打印所有可能的真值组合。 相当于求长度为n的位串有多少种。旧文用的方法太蛋疼了，位串长度稍稍增大，运行时间就变得不可接受了(那个时候还是图样啊)，现在我尝试着写个好一点的。

先贴个旧版的蛋疼代码:

#include <stdio.h>

/*
 * 给定n个布尔变量(x[1]...x[n]),打印所有可能的真值组合.
 * 例如: n = 2时, 共有四种可能:
 *     (true, true),(true, false),(false, true),(false, false)
 *
 *  Warning:请不要输入太大的 n 值，因为打印所需的时间是相当的可观;
 *          当 n = 25, 每秒打印100种组合, 大约需要4天......
 * */
void print_sequence(int n)
{
    //n应该大于0.
    if ( n <= 0 )
    {
        return;
    }
    int count = (1 << n);//组合数量计数器,即共有count种组合.
    int binary_bits = 0;//(111,101,010...)布尔组合的位串.
                        //因为机器原因,最多只能表示30位(有符号int类型的数据位).
                        //你输入31就知道了<^_^>.
                        //可以改用long, or long long以增加数据位,
                        //同时count也要改.(那么长的位串,时间要以年计算了,呵呵).
    int i, j, bit;
    for (i = 0; i < count; i ++)
    {
        binary_bits = i;
        printf("(");
        for (j = 0; j < n; ++j)
        {
            bit = binary_bits % 2;
            if (bit)
            {
                printf("TRUE");
            }
            else
            {
                printf("FALSE");
            }
            if ( j < (n - 1) )
            {
                printf(", ");
            }
            binary_bits >>= 1;
        }
        printf(")\n");
    }
}

//Application start
int main(void)
{
    int amount = 0;
    do
    {
        printf("Input amount of boolean varibles:");
        scanf("%d", &amount);
    } while(amount <= 0);
    print_sequence(amount);

    getch();
    return 0;
}
                
                

复杂度是O(2ⁿ)，因此速度方面必然不会太快。 记得后来得知求模运算特别慢，就试着把其中的bit = binary_bits % 2;改成位运算代替， 谁知对速度几乎没影响<T_T>。最近半年里翻过 《深入理解计算机系统》(Computer System A programmer's Perspective, 2nd) 之后，才发现 那个求模的开销，和调用printf()这样的I/O函数相比，连个屁都不算! 而且现代的CPU从硬件上已经极大的优化了除法所用的CPU周期。I/O开销才是我这里改进的重点。 我在这里调用太多次printf()了。

下面说说改进吧。 如果用了一个 缓存区，将需要输出的字符"组装"成一个字符串，那么就只需要调用一次 打印函数。不过我需要知道: 我需要一个多大的缓存区。 一次缓存所有的输出似乎很好, 但是如果n很大，我觉得缓冲区就太大了，故不敢如此。 而且这个算法本身的时间复杂度就很大, 当n很大时, 你再怎么减小I/O开销也没有大作用了。 最后决定 每次缓存一行，这样感觉各个方面都可以接受。 在我的输出格式里，如果输入是n， 那么 括号就需要2个字符，用于分隔真值的字符", "占用的空间是 2(n-1)，一个"TRUE"需要4个字符，而一个"FALSE"需要5个，考虑最坏情况(全是FALSE)，保留5n个字符的空间，最后'\n'， '\0'各占一个，一共需要7n + 2个字符空间。

说那么多，最后还是要看代码的:

#include <stdio.h>

/*
 * 给定n个布尔变量(x[1]...x[n]),打印所有可能的真值组合.
 * 例如: n = 2时, 共有四种可能:
 *     (true, true),(true, false),(false, true),(false, false)
 *
 *  Warning:请不要输入太大的 n 值，虽然这个是优化过的程序, 但是这里的时间复杂度还是O(2^n);
            所以要想从根本改进性能, 还是换个时间复杂度较低的算法吧(反正我现在是不会, 呵呵)
 *          当 n = 25, 每秒打印100种组合, 大约需要4天......
 * */
void print_sequence(int n)
{
    //n应该大于0.
    if ( n <= 0 )
    {
        return;
    }

    /*
    *我这里使用一个字符数组作为缓存，
    *数组的大小根据位串长度n来动态计算,
    *根据我这里的输出格式, 得出的公式是 7n + 2,
    *把要输出的字符"组装"后, 一次输出一行,
    *这样可以大大减少 调用printf之类的I/O函数的频率,
    *因为它们的开销相对(开辟一块数组空间,及后续"组装"字符串)来说太大了
    */
    int len = 7 * n + 2;
    char str[len];//"动态大小"数组, 记得是C99的特性

    str[0] = '(';
    str[len - 1] = '\0';//加这个主要是防止下面忘记结束字符串, 其实挺多余的

    int count = (1 << n);//组合数量计数器,即共有count种组合.
    int binary_bits = 0;//(111,101,010...)布尔组合的位串.
                        //因为我这里int类型是32位的,所以最多只能表示30位
                        //你输入32就知道了<^_^>.
                        //可以改用long, or long long以增加数据位,
                        //同时count也要改.(那么长的位串,时间要以年计算了,呵呵).
    int i, j, bit;
    for (i = 0; i < count; i ++)
    {
        int index = 1;
        binary_bits = i;

        for (j = 0; j < n; ++j)
        {
            bit = binary_bits & 1;
            binary_bits >>= 1;
            if (bit)
            {
                //输出"TRUE"
                str[index++] = 'T';
                str[index++] = 'R';
                str[index++] = 'U';
                str[index++] = 'E';
            }
            else
            {
                //输出"FALSE"
                str[index++] = 'F';
                str[index++] = 'A';
                str[index++] = 'L';
                str[index++] = 'S';
                str[index++] = 'E';
            }
            if ( j < (n - 1) )
            {
                //使用", "隔开相邻的真值
                str[index++] = ',';
                str[index++] = ' ';
            }
        }
        str[index++] = ')';
        str[index] = '\0';//加个结束符

        //only print here
        puts(str);
    }
}

//Application start
int main(void)
{
    int amount = 11;
    /*int amount = 0;
    do
    {
        printf("Input amount of boolean varibles:");
        scanf("%d", &amount);
    } while(amount <= 0);*/
    print_sequence(amount);

    //getch();
    return 0;
}

                
                

最后看一看效果，还是比较明显的。以下是在CodeBlocks中的执行时间，每个输入运行三次。

当输入是11时，改进前：2.415s, 2.416s, 2.420s。 改进后：0.555s, 0.539s, 0.570s。

当输入是15时，改进前：46.284s, 46.149s, 46.699s。 改进后：4.762s, 4.772s, 4.646s

即使当输入是3时， 改进前：0.011s, 0.011s, 0.011s。 改进后：0.007s, 0.007s, 0.007s。

最快可以快10倍以上，这个结果，我还是很满意的。

旧文链接: 打印所有真值组合的练习题