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

1、C 语言程序设计100 例之(31) ：全排列问题例 31 全排列问题题目描述输出自然数1 到 n 所有不重复的排列，即n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。输入格式n(1 < n < 9)输出格式由1n组成的所有不重复的数字序列，每行一个序列。序列中每个数字占 5个宽度。输入样例3输出样例1 232 323 134 315 126 21( 1)编程思路。采用递归的方法来生成全排列。(2)源程序。#include <stdio.h>int a9,flag10=0;void dfs(int pos,int n)if (pos=n) / 已有 n 个

2、数for (int i=0;i<n;i+)printf("%5d",ai);printf("n");elsefor(int i=1;i<=n;i+)if(flagi)continue;apos=i;flagi=1;dfs(pos+1,n);flagi=0;int main()int n;scanf("%d",&n);dfs(0,n);return 0;习题 3131-1 选书本题选自洛谷题库( /problem/P1657 )题目描述学校放寒假时，信息学奥赛辅导老师有1,2,

3、3x本书，要分给参加培训的x个人，每人只能选一本书，但是每人有两本喜欢的书。老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。输入格式第 1 行：一个数x第2行第1+x行：每行两个数，表示 ai喜欢的书的序号输出格式只有一个数：总方案数total 。输入样例51 34 52 51 43 5输出样例2( 1)编程思路。编写递归函数 void dfs(int i,int n)表示第i个人在n本书中选择一本书。若第 j本书(1W jwn)没选(标记数组元素fj=1 )且第i个人喜欢这本书(数组元素aij的值

4、也为1),则第 i 个人选择第j 本书； 之后第 i+1 个人进行选择，递归调用dfs(i+1,n)。 若 n 个人均选择好，则计数。( 2)源程序。#include <stdio.h>int a2121,f21,cnt;/ aij第 i 个人喜欢第 j 本书void dfs(int i,int n) int j;for(j=1;j<=n;j+) if(fj && aij) / 这本书没选且第i 个人喜欢这本书fj=0; if(i=n) cnt+; else dfs(i+1,n); fj=1; int main() int n,i,x,y;scanf(&quo

5、t;%d",&n);for(i=1;i<=n;i+) scanf("%d%d",&x,&y); aix=1;aiy=1;fi=1; dfs(1,n); printf("%dn",cnt); return 0;31-2 差三角形问题描述观察下面的数字组成的三角形：31 45 6 2看出什么特征吗？1 )它包含了16 的连续整数。2)每个数字都是其下方相邻的两个数字的差(当然是大数减去小数)满足这样特征的三角形，称为差三角形。编写程序，找出由1n*(n+1)/2 共 n*(n+1)/2 个整数组成的一个差三角形。输入格

6、式一个正整数n。n w 6输出格式输出所有满足要求的差三角形。输出时，每个数字占4 列。每种解之间空一行。当无解的时候，请什么也不输出。输入样例4输出样例434 75 926 110837 28 979 1018410 611 7112 3 1094512768 1039( 1 )编程思路。先确定最后一行的值，即在1 n*(n+1)/2 这 n*(n+1)/2 个数中任意选取n 个元素进行全 排列。 之后，按差三角形的特征依次确定上面其它行的值。在确定值的过程中，若某个值已被使用，则不可能是问题的解。直接剪枝，进行下次搜索。( 2)源程序。#include <stdio.h>voi

7、d judge(int take,int n)int visited22; / 最多 6 行， 21 个数int num66,i,j,x;for (i=1;i<=n*(n+1)/2;i+)visitedi=0;for(i = 0; i < n; i+)numn-1i=takei;visitedtakei = 1;for (i=n -2; i>=0; i -)for (j = 0; j <= i; j+)x = abs(numi+1j - numi+1j+1); if(visitedx)return;if(x>=1 && x<= n*(n+1)

8、/2)visitedx = 1;numij = x;if (numn -10>numn -1n-1) return ; for (i = 0; i < n; i+)for(j = 0; j<=i; j+)printf("%4d",numij);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;

9、i+)if(!visi)visi = 1;takeindex= i;dfs(take, index+1,vis,n); visi = 0;int main()int n,take6,i;int vis22;scanf("%d",&n);for(i = 1; i <= n*(n+1)/2; i+) visi=0;dfs(take,0,vis,n);return 0;31-3 数字和问题描述写出一个1至n的排列ai,a2,an,然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面

10、是一个例子：3 ,1,2,44,3,67,916最后得到16 这样一个数字。如果知道n和最后得到的数字的大小sum,请你求出最初序列ai,a2,an,这个序列为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 w I2,sumw 12345。输出格式输出包括1 行，为字典序最小的那个答案。当无解的时候，请什么也不输出。输入样例4 16输出样例3 1 2 4( 1)编程思路。以题目示例来说明。4 个数 a1 、

11、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行的值，以便于最后总和的计算。生成 1n 的全排列，对生成的排列进行判断，看是否满足和值等于输入的sum， 如果找到的答案，置标记found 为 1 ，之后各排列直接返回。( 2)源程序。#include <stdio.h>int a12,flag13=0,y13=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 ",ai);printf("n");found=1;elsefor(int i=1;i<=n;i+)if(flagi)continue;apos=i;flagi=1;df