C语言程序设计100例之（31）：全排列问题

例31   全排列问题

题目描述

输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

n(1≤n≤9)

输出格式

由1～n组成的所有不重复的数字序列，每行一个序列。序列中每个数字占5个宽度。

输入样例

3

输出样例

    1    2    3

    1    3    2

    2    1    3

    2    3    1

    3    1    2

    3    2    1

       （1）编程思路。

       采用递归的方法来生成全排列。

        （2）源程序。

#include <stdio.h>

int a[9],flag[10]={0};

void dfs(int pos,int n)

{

     if (pos==n)  // 已有n个数

     {

         for (int i=0;i<n;i++)

            printf("%5d",a[i]);

         printf("\n");

     }

     else

     {

         for(int i=1;i<=n;i++)

         {

            if(flag[i])

                continue;

            a[pos]=i;

            flag[i]=1;

            dfs(pos+1,n);  

            flag[i]=0;

         }

     }

}

int main()

{

    int n;

    scanf("%d",&n);

    dfs(0,n);

    return 0;

}

习题31

31-1  选书

        本题选自洛谷题库 （https://www.luogu.org/problem/p1657）

题目描述

学校放寒假时，信息学奥赛辅导老师有1,2,3……x本书，要分给参加培训的x个人，每人只能选一本书，但是每人有两本喜欢的书。老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。

输入格式

第1行：一个数x

第2行~第1+x行：每行两个数，表示ai喜欢的书的序号

输出格式

只有一个数：总方案数total。

输入样例

5

1 3

4 5

2 5

1 4

3 5

输出样例

2

        （1）编程思路。

        编写递归函数void dfs(int i,int n)表示第i个人在n本书中选择一本书。若第j本书（1≤j≤n）没选（标记数组元素f[j]=1）且第i个人喜欢这本书（数组元素a[i][j]的值也为1），则

第i个人选择第j本书；之后第i+1个人进行选择，递归调用dfs(i+1,n)。若n个人均选择好，则计数。

        （2）源程序。

#include <stdio.h>

int a[21][21],f[21],cnt;  // a[i][j]第i个人喜欢第j本书

void dfs(int i,int n)

{

         int j;

         for(j=1;j<=n;j++)

         {

                   if(f[j] && a[i][j]) // 这本书没选且第i个人喜欢这本书

                   {

                            f[j]=0;

                            if(i==n)

                            {

                                     cnt++;

                            }

                            else

                            {

                                     dfs(i+1,n);

                            }

                            f[j]=1;

                   }

         }

}

int main()

{

         int n,i,x,y;

         scanf("%d",&n);

         for(i=1;i<=n;i++)

         {

                   scanf("%d%d",&x,&y);

                   a[i][x]=1;

                   a[i][y]=1;

                   f[i]=1;

         }

         dfs(1,n);

         printf("%d\n",cnt);

         return 0;

} 

31-2  差三角形

问题描述

观察下面的数字组成的三角形：

        3

       1 4

      5 6 2

看出什么特征吗？

1）它包含了1~6的连续整数。

2）每个数字都是其下方相邻的两个数字的差（当然是大数减去小数）

满足这样特征的三角形，称为差三角形。

编写程序，找出由1~n*(n+1)/2共n*(n+1)/2个整数组成的一个差三角形。

输入格式

一个正整数n。n≤6

输出格式

输出所有满足要求的差三角形。输出时，每个数字占4列。每种解之间空一行。

当无解的时候，请什么也不输出。

输入样例

4

输出样例

4

   3

   4   7

   5   9   2

   6   1  10   8

 

   3

   5   2

   4   9   7

   6  10   1   8

 

   4

   2   6

   5   7   1

   8   3  10   9

 

   4

   5   1

   2   7   6

   8  10   3   9

 

      （1）编程思路。

      先确定最后一行的值，即在1~ n*(n+1)/2这n*(n+1)/2个数中任意选取n个元素进行全排列。之后，按差三角形的特征依次确定上面其它行的值。在确定值的过程中，若某个值已被使用，则不可能是问题的解。直接剪枝，进行下次搜索。

       （2）源程序。

#include <stdio.h>

void judge(int take[],int n)

{

    int visited[22];  // 最多6行，21个数

    int num[6][6],i,j,x;

    for (i=1;i<=n*(n+1)/2;i++)

        visited[i]=0;

    for(i = 0; i < n; i++)

    {

        num[n-1][i]=take[i];

        visited[take[i]] = 1;

    }

    for (i=n-2; i>=0; i--)

       for (j = 0; j <= i; j++)

       {

           x = abs(num[i+1][j] - num[i+1][j+1]);

           if(visited[x])

               return;

           if(x>=1 && x<= n*(n+1)/2)

           {

               visited[x] = 1;

               num[i][j] = x;

           }

       }

       if  (num[n-1][0]>num[n-1][n-1]) return ;

       for (i = 0; i < n; i++)

       {

           for(j = 0; j<=i; j++)

               printf("%4d",num[i][j]);

           printf("\n");

       }

       printf("\n");

}

void dfs(int take[], int index,int vis[],int n)

{

    int i, j;

    if (index==n)

    {

        judge(take,n);

        return;

    }

    for(i = 1; i <= n*(n+1)/2; i++)

    {

        if(!vis[i])

        {

            vis[i] = 1;

            take[index]= i;

            dfs(take, index+1,vis,n);

            vis[i] = 0;

        }

    }

}

int main()

{

    int n,take[6],i;

    int vis[22];

    scanf("%d",&n);

    for(i = 1; i <= n*(n+1)/2; i++)

       vis[i]=0;

    dfs(take,0,vis,n);

    return 0;

} 

31-3 数字和

问题描述

写出一个1至n的排列a₁,a₂,…,a_n，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：

3 ,1,2,4

4,3,6

7,9

16

最后得到16这样一个数字。

如果知道n和最后得到的数字的大小sum，请你求出最初序列a₁,a₂,…,a_n，这个序列为1至n的一个排列。若答案有多种可能，则输出字典序最小的那一个。

注意：本题字典序指的是1,2,3,4,5,6,7,8,9,10,11,12，而不是1,10,11,12,2,3,4,5,6,7,8,9。

输入格式

两个正整数n,sum。n≤12,sum≤12345。

输出格式

输出包括1行，为字典序最小的那个答案。

当无解的时候，请什么也不输出。

输入样例

4 16

输出样例

3 1 2 4

        （1）编程思路。

        以题目示例来说明。4个数a1、a2、a3、a4

        第1次得到： a1+a2、a2+a3、a3+a4

        第2次得到：a1+a2+a2+a3、a2+a3+a3+a4

        第3次得到：(a1+a2+a2+a3)+(a2+a3+a3+a4)

        即最后总和为：a1+3*a2+3*a3+a4

        系数1、3、3、1正好四杨辉三角形的第4行的值。因此，需要先求出杨辉三角形第n行的值，以便于最后总和的计算。

        生成1~n的全排列，对生成的排列进行判断，看是否满足和值等于输入的sum，如果找到的答案，置标记found为1，之后各排列直接返回。

        （2）源程序。

#include <stdio.h>

int a[12],flag[13]={0},y[13]={0};

int n,sum,found=0;

void dfs(int pos,int cursum)

{

     if (cursum>sum|| found==1) return;

     if (pos==n) 

     {

         if (cursum==sum)

         {

            for (int i=0;i<n;i++)

               printf("%d ",a[i]);

            printf("\n");

            found=1;

         }

     }

     else

     {

         for(int i=1;i<=n;i++)

         {

            if(flag[i])

                continue;

            a[pos]=i;

            flag[i]=1;

            dfs(pos+1,cursum+a[pos]*y[pos]);

            flag[i]=0;

         }

     }

}

int main()

{

    scanf("%d%d",&n,&sum);

    y[0]=1;

    for (int row=1;row<n;row++)

        for (int col=row;col>=1;col--)

            y[col]=y[col]+y[col -1];

    dfs(0,0);

    return 0;

}