The Hamming Distance Problem UVA 729 （01串的全排列）
来源：程序员人生 发布时间：2014-10-03 08:00:01 阅读次数：3167次
说说：
这题的意思就是给你一个01串的总长度和其中1的个数，要你求出该串的所有排列，并按照字典升序输出。其实这道题和前一道Generating Fast是非常类似的，甚至更为简单。要做的就是一个DFS给每个位分配位置，若0没有用完，则先分配0。1没有用完，则接着分配1。最后将结果输出即可。
源代码：
#include <stdio.h>
#define MAX 16+5
int N,H,onum,znum;
char p[MAX];
void dfs(int,int,int);
int main(){
int T;
// freopen("data","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&H);
znum=N-H;//0的个数
onum=H;//1的个数
p[N]=' ';
dfs(0,0,0);
if(T) putchar('
');
}
return 0;
}
void dfs(int num1,int num0,int cur){
int c1,c2,i;
if(cur==N){
printf("%s
",p);
return;
}
c1=c2=0;
if(num0<znum){//0未用完，则先放0
p[cur]='0';
dfs(num1,num0+1,cur+1);
}
if(num1<onum){//1未用完，则再放1
p[cur]='1';
dfs(num1+1,num0,cur+1);
}
return;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
