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

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

2、,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,3x 本书， 要分给参加培训的x 个人，每人只能选一本书， 但是每人有两本喜欢的书。老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书

3、本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。输入格式第 1 行：一个数x第 2 行 第 1+x 行：每行两个数，表示ai 喜欢的书的序号输出格式只有一个数：总方案数total 。输入样例51 34 52 51 43 5输出样例2（ 1）编程思路。编写递归函数void dfs(int i,int n)表示第i 个人在 n 本书中选择一本书。若第j 本书（ 1j n）没选（标记数组元素fj=1 ）且第 i 个人喜欢这本书（数组元素aij 的值也为1 ），则第 i 个人选择第 j 本书；之后第 i+1 个人进行选择， 递归调用 dfs(i+1,n)。若 n 个人均选择好，则

4、计数。（ 2）源程序。#include 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+;elsedfs(i+1,n);fj=1;int main()int n,i,x,y;scanf(%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差三角形问题描述观察下

5、面的数字组成的三角形：31 45 6 2看出什么特征吗？1）它包含了16 的连续整数。2）每个数字都是其下方相邻的两个数字的差（当然是大数减去小数）满足这样特征的三角形，称为差三角形。编写程序，找出由1n*(n+1)/2 共 n*(n+1)/2 个整数组成的一个差三角形。输入格式一个正整数n 。n 6输出格式输出所有满足要求的差三角形。输出时，每个数字占4 列。每种解之间空一行。当无解的时候，请什么也不输出。输入样例4输出样例434759261108352497610184265718310945127681039（ 1）编程思路。先确定最后一行的值，即在1 n*(n+1)/2 这 n*(n+

6、1)/2 个数中任意选取n 个元素进行全排列。 之后，按差三角形的特征依次确定上面其它行的值。在确定值的过程中，若某个值已被使用，则不可能是问题的解。直接剪枝，进行下次搜索。（ 2）源程序。#include void 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 =0; i - )for (j = 0; j =1 & xnumn -1n -1) return ;for (i = 0; i n; i+)for(j =

7、 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; 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

8、; i+)visi=0;dfs(take,0,vis,n);return 0;31-3 数字和问题描述写出一个 1 至 n 的排列 a1,a2,an，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少位置。下面是一个例子：3 ,1,2,44,3,67,916最后得到 16 这样一个数字。如果知道 n 和最后得到的数字的大小sum，请你求出最初序列a12n至,a,a，这个序列为1n 的一个排列。若答案有多种可能，则输出字典序最小的那一个。注意：本题字典序指的是1,2,3,4,5,6,7,8,9,10,11,12 ，而不是1,10,11,12

9、,2,3,4,5,6,7,8,9 。输入格式两个正整数n,sum 。n 12,sum 12345。输出格式输出包括 1 行，为字典序最小的那个答案。当无解的时候，请什么也不输出。输入样例4 16输出样例3124（ 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 行的值。因此，需要先求出杨辉三

10、角形第n行的值，以便于最后总和的计算。生成 1n 的全排列， 对生成的排列进行判断，看是否满足和值等于输入的sum，如果找到的答案，置标记found 为 1，之后各排列直接返回。（ 2）源程序。#include int a12,flag13=0,y13=0;int n,sum,found=0;void dfs(int pos,int cursum)if (cursumsum| found=1) return;if (pos=n)if (cursum=sum)for (int i=0;in;i+)printf(%d ,ai);printf(n);found=1;elsefor(int i=1;i=n;i+)if(flagi)