国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > The Hamming Distance Problem UVA 729 (01串的全排列)

The Hamming Distance Problem UVA 729 (01串的全排列)

来源:程序员人生   发布时间:2014-10-03 08:00:01 阅读次数:3164次

说说:

这题的意思就是给你一个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; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生