笔记(二进制枚举)

mac2024-12-06  44

二进制枚举

假设有n个数字分别为{a1,a2,a3…,an},我要从中选出k个(1=<k<=n),则

根据二项展开式系数和:C(0,n)+C(1,n)+……+C(n,n)=2^n,

共有2^n种选法。

二进制枚举即可用二进制数表示出这几种选择方法。

0表示不选,1表示选。

然后用代码实现:

int temp[100][100]; for(int i=0;i<=(1<<n)-1;i++) { for(int j=0;j<=n-1;j++) { temp[1][n-j] = (i>>j)&1; } }

例:

假设n=3;{a1,a2,a3};

共有 2^3 = 8 种。

1: i=0,temp[1][……]={1 , 1 , 1 };

2: i=1,temp[1][……]={0 , 1 , 1 };

3: i=2,temp[1][……]={1 , 0 , 1 };

4: i=3,temp[1][……]={0 , 0 , 1 };

5: i=4,temp[1][……]={1 , 1 , 0 };

6: i=5,temp[1][……]={0 , 1 , 0 };

7: i=6,temp[1][……]={1 , 0 , 0 };

8: i=7,temp[1][……]={0 , 0 , 0 };

☆ (i>>j)&1 二进制拆分

2019.10.31 By October

最新回复(0)