一　、全排列问题(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
     
      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("\n");                                }                                num[i2-1]=0;                            }                    }        else        {            for(i=0;i<1;i++)            {                printf("%d ",ans[i]);            }            printf("\n");        }        num[i1-1]=0;    }    return 0;}
     

 

　　这是挺麻烦的……

　　3.属于2的代码简化版，用函数的递归来缩短代码长度：

#include
     
      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
     

 

　　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
     
      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，这样它就和第一题解法一模一样了。（回溯）