一 、全排列问题(Form.cpp)
【问题描述】
输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
【输入格式】
n(1≤n≤9)
【输出格式】
由1～n组成的所有不重复的数字序列，每行一个序列。(字典序排列)
【输入样例】Form.in
3
【输出样例】Form.out
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
【解析】
1.看到n只有1~9，那么最简单的方法就是：自己算出9种情况的答案，然后一个一个if来输出，对于本题一定是满分；
2.用9个for来计算答案：
#include<stdio.h> int main() { int ans[9]; int num[9]={0};//用做记录此数字是否被用过 int i,i1,i2,i3,i4,i5,i6,i7,i8,i9; int n; scanf("%d",&n); for(i1=1;i1<=n;i1++)//第一层循环 { if(num[i1-1]==1) continue; ans[0]=i1; num[i1-1]=1;//标记 if(n>=2) { for(i2=1;i2<=n;i2++)//第二层循环 { if(num[i2-1]==1) continue; ans[1]=i2; num[i2-1]=1;//标记 if(n>=3) { //第三层循环………… } else { for(i=0;i<2;i++) { printf("%d ",ans[i]); } printf(" "); } num[i2-1]=0; } } else { for(i=0;i<1;i++) { printf("%d ",ans[i]); } printf(" "); } num[i1-1]=0; } return 0; }
这是挺麻烦的……
3.属于2的代码简化版，用函数的递归来缩短代码长度：
#include<stdio.h> int n; int ans[9]; int num[9]={0};//用做记录此数字是否被用过 int search(int level); int main() { scanf("%d",&n); search(n); return 0; } int search(int level)//level从n~0进行递归 { if(level==0)//到顶了 { int i; for(i=0;i<n;i++)//输出 { printf("%d ",ans[i]); } printf(" "); return 0; } else { int i; for(i=1;i<=n;i++) { if(num[i-1]==1) continue; num[i-1]=1; ans[n-level]=i; search(level-1); num[i-1]=0;//两行刷黄的代码属于典型的回溯
//即“将每一层递归获得的结果保存在一个数组内，等递归结束返回时，再将结果复原” 的思想
//有利于递归时保存数据 } return 0; } }
PS:在search函数的else中的for里，从1-n的循环有助于将答案按照字典序输出。
2、组合的输出(Compages.cpp)
【问题描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r<＝n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
现要求你用递归的方法输出所有组合。
例如n＝5，r＝3，所有组合为：
l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
【输入】
一行两个自然数n、r(1<n<21，1<＝r<＝n)。
【输出】
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
【样例】
输入：5 3
输出： 1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
【解析】
此题与第一题极为相似，当这里 n==r 时，就是第一题的解法。
然而这里的r不一定与n相等，大家对比一下第一题的程序，发现有什么变化了吗？
火眼金睛大比拼：
#include<stdio.h> int n,r; int ans[9]; int num[9]={0};//用做记录此数字是否被用过 int search(int level); int main() { scanf("%d%d",&n,&r); search(r); return 0; } int search(int level) { if(level==0)//到顶了 { int i; for(i=0;i<r;i++) { printf("%d ",ans[i]); } printf(" "); return 0; } else { int i; for(i=1;i<=n;i++) { if(num[i-1]==1) continue; num[i-1]=1; ans[r-level]=i; search(level-1); num[i-1]=0; } return 0; } }
没错，我们将控制 寻找数字个数 的变量全部换成了r，这样它就和第一题解法一模一样了。（回溯）