ACM之递归组合【递归很重要】.docVIP

递归求解几类排列组合问题Welcome to JudgeOnline 对于有哪些信誉好的足球投注网站的深度很深或深度不固定的情况，则无法用枚举的方法来设置循环嵌套的层数，这时可以考虑用递归法来完成有哪些信誉好的足球投注网站任务。递归是一种常用算法，它是有哪些信誉好的足球投注网站的另一种实现方式。如果在算法设计中采用一个函数或过程直接或间接地调用它自身来解决问题的方法，则称该方法为递归算法。递归算法必须要设计好一个或若干个确定的递归终止条件。 Sample Input： 4 2 Sample Output 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111Program #includestdio.h int n,m; int mat[10]; void solve(int l){ if(l=n){ for(int i=0;in;++i)printf(%d, mat[i]); puts(); return; } for(int i=0;im;++i){ mat[l]=i; solve(l+1); } } int main(){ while(scanf(%d%d, n, m)!=EOF){ solve(0); } return 0; } 二、全组合排列 Sample Input 3 1 2 3 Sample Output 123 132 213 231 312 321 //Program #includestdio.h #includestring.h const int maxn=11; int n; int used[maxn];//标记数组 int mat[maxn];//存储数组 int num[maxn];//输出数组 void solve(int l){ if(l=n){ for(int i=0;in;++i)printf(%d, num[i]); puts(); return; } for(int i=0;in;++i){ if(!used[i]){ used[i]=1; num[l]=mat[i]; solve(l+1); used[i]=0; } } } int main(){ while(scanf(%d, n)!=EOF){ for(int i=0;in;++i)scanf(%d, mat+i); memset(used,0,sizeof(used)); solve(0); } return 0; } 三、非重复组合排列（含重复数字时，生成不重复组合排列） Sample Input 4 1 2 2 3 Sample Output 1223 1232 1322 2123 2132 2213 2231 2312 2321 3122 3212 3221 //Program #includestdio.h const int maxn=10; int n,var; int Index; int used[maxn],mat[maxn],num[maxn]; void push(int varNum){ //压栈 for(int i=0;iIndex;++i){ if(mat[i]==varNum){ ++used[i]; return; } } mat[Index]=varNum; ++used[Index++]; } void solve(int l){ //求解 if(l=n){ for(int i=0;in;++i)printf(%d, num[i]); puts(); return; } for(int i=0;iIndex;++i){ if(used[i]){ used[i]--; num[l]=mat[i]; solve(l+1); used[i]++; } } } int main(){ whil