首页 > 代码库 > UVa 729 - The Hamming Distance Problem

UVa 729 - The Hamming Distance Problem

题目:构造n位01串,其中有m个1的所有组合。

分析:搜索、枚举。可以利用库函数,求解,也可以利用dfs求解;我这里采用位运算计算组合数。

说明:注意库啊!

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int S[20];

int main()
{
	int T,N,M;
	while ( cin >> T )
	for ( int t = 1 ; t <= T ; ++ t ) {
		if ( t > 1 ) printf("\n");
		
		cin >> N >> M;
		int xx,yy,comb = (1<<M)-1,j,count;  
        while ( comb < (1<<N) ) {  
            /* 计算当前状态对应的集合 */   
            j = 0; count = 0;
            do {  
                S[count ++] = ((1<<j)&comb)>0;  
                j ++;  
            }while ( j < N ); 
			while ( count -- )
				printf("%d",S[count]); 
            printf("\n");
            /* 位运算计算下一集合,按照顺序递增 */   
            xx = comb&-comb,yy = comb+xx;  
            comb = ((comb&~yy)/xx>>1)|yy;  
        }
	}
	
	return 0;  
}