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)