n个位置上放置0和1问题

Date:2012-10-29

好吧.貌似我最近光研究这个问题了..

特殊版本必然有特殊的解决办法.

另外必须要提及一个问题(来自sf):

罗列出qwerty被.分割的所有情况：

q.werty
q.w.erty
qw.erty
...
q.w.e.r.t.y

不难发现, 这个问题要解决的就是我们这个问题:n个位置上放置0和1

在这个问题中, 有个大牛给出的代码:

#define z(a,b) printf(#a"%s",(x>>b)&1?".":""),
main(x){z(a,3)z(b,2)z(c,1)z(d,0)puts("e");16-x&&main(x+1);}

或者针对于咱们的一般化问题的话:

#include <stdio.h>
#define N 3
main(x){
    int i;  
    for (i = 0; i<N;printf("%d",x >> i &1), i++); 
    printf("\n");
    (1 << N)-x && main(x+1); 
    return 0; 
}

下面的是一个比较容易理解的函数版本

void foo(unsigned int n)
{
    int i, j, k; 
    for (i = 0; i < 1 << n; printf("\n"), i++)
        for (j = 0, k = i; j < n; printf("%d", k&1), k >>= 1, j++); 
}

算法思想:

对于n个元素的情形, 共有2^n个可能情况.每个情况对应于一个二进制数.所有的情况的二进制数是0~2^n-1
对于每个比2^n小的数i:
    打印i的二进制形式, 怎么打印呢:
    k = i, k跟1取与操作即可得到k的最后一位, 然后k右移1.直到n个位置全部打印

对于那个大牛代码中的一些细节:

main(x)中的 x会初始化为1(参数个数)
宏中的#作用见文章C语言宏定义中的井号#