C語(yǔ)言程序設(shè)計(jì)100例之(31)：全排列問(wèn)題

1、C 語(yǔ)言程序設(shè)計(jì)100 例之(31) ：全排列問(wèn)題例 31 全排列問(wèn)題題目描述輸出自然數(shù)1 到 n 所有不重復(fù)的排列，即n 的全排列，要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字。輸入格式n(1 < n < 9)輸出格式由1n組成的所有不重復(fù)的數(shù)字序列，每行一個(gè)序列。序列中每個(gè)數(shù)字占 5個(gè)寬度。輸入樣例3輸出樣例1 232 323 134 315 126 21( 1)編程思路。采用遞歸的方法來(lái)生成全排列。(2)源程序。#include <stdio.h>int a9,flag10=0;void dfs(int pos,int n)if (pos=n) / 已有 n 個(gè)

2、數(shù)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;習(xí)題 3131-1 選書(shū)本題選自洛谷題庫(kù)( /problem/P1657 )題目描述學(xué)校放寒假時(shí)，信息學(xué)奧賽輔導(dǎo)老師有1,2,

3、3x本書(shū)，要分給參加培訓(xùn)的x個(gè)人，每人只能選一本書(shū)，但是每人有兩本喜歡的書(shū)。老師事先讓每個(gè)人將自己喜歡的書(shū)填寫(xiě)在一張表上。然后根據(jù)他們填寫(xiě)的表來(lái)分配書(shū)本，希望設(shè)計(jì)一個(gè)程序幫助老師求出所有可能的分配方案，使每個(gè)學(xué)生都滿意。輸入格式第 1 行：一個(gè)數(shù)x第2行第1+x行：每行兩個(gè)數(shù)，表示 ai喜歡的書(shū)的序號(hào)輸出格式只有一個(gè)數(shù)：總方案數(shù)total 。輸入樣例51 34 52 51 43 5輸出樣例2( 1)編程思路。編寫(xiě)遞歸函數(shù) void dfs(int i,int n)表示第i個(gè)人在n本書(shū)中選擇一本書(shū)。若第 j本書(shū)(1W jwn)沒(méi)選(標(biāo)記數(shù)組元素fj=1 )且第i個(gè)人喜歡這本書(shū)(數(shù)組元素aij的值

4、也為1),則第 i 個(gè)人選擇第j 本書(shū)； 之后第 i+1 個(gè)人進(jìn)行選擇，遞歸調(diào)用dfs(i+1,n)。 若 n 個(gè)人均選擇好，則計(jì)數(shù)。( 2)源程序。#include <stdio.h>int a2121,f21,cnt;/ aij第 i 個(gè)人喜歡第 j 本書(shū)void dfs(int i,int n) int j;for(j=1;j<=n;j+) if(fj && aij) / 這本書(shū)沒(méi)選且第i 個(gè)人喜歡這本書(shū)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 差三角形問(wèn)題描述觀察下面的數(shù)字組成的三角形：31 45 6 2看出什么特征嗎？1 )它包含了16 的連續(xù)整數(shù)。2)每個(gè)數(shù)字都是其下方相鄰的兩個(gè)數(shù)字的差(當(dāng)然是大數(shù)減去小數(shù))滿足這樣特征的三角形，稱為差三角形。編寫(xiě)程序，找出由1n*(n+1)/2 共 n*(n+1)/2 個(gè)整數(shù)組成的一個(gè)差三角形。輸入格

6、式一個(gè)正整數(shù)n。n w 6輸出格式輸出所有滿足要求的差三角形。輸出時(shí)，每個(gè)數(shù)字占4 列。每種解之間空一行。當(dāng)無(wú)解的時(shí)候，請(qǐng)什么也不輸出。輸入樣例4輸出樣例434 75 926 110837 28 979 1018410 611 7112 3 1094512768 1039( 1 )編程思路。先確定最后一行的值，即在1 n*(n+1)/2 這 n*(n+1)/2 個(gè)數(shù)中任意選取n 個(gè)元素進(jìn)行全 排列。 之后，按差三角形的特征依次確定上面其它行的值。在確定值的過(guò)程中，若某個(gè)值已被使用，則不可能是問(wèn)題的解。直接剪枝，進(jìn)行下次搜索。( 2)源程序。#include <stdio.h>voi

7、d judge(int take,int n)int visited22; / 最多 6 行， 21 個(gè)數(shù)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 數(shù)字和問(wèn)題描述寫(xiě)出一個(gè)1至n的排列ai,a2,an,然后每次將相鄰兩個(gè)數(shù)相加，構(gòu)成新的序列，再對(duì)新序列進(jìn)行這樣的操作，顯然每次構(gòu)成的序列都比上一次的序列長(zhǎng)度少1，直到只剩下一個(gè)數(shù)字位置。下面

10、是一個(gè)例子：3 ,1,2,44,3,67,916最后得到16 這樣一個(gè)數(shù)字。如果知道n和最后得到的數(shù)字的大小sum,請(qǐng)你求出最初序列ai,a2,an,這個(gè)序列為1至n 的一個(gè)排列。若答案有多種可能，則輸出字典序最小的那一個(gè)。注意：本題字典序指的是1,2,3,4,5,6,7,8,9,10,11,12，而不是1,10,11,12,2,3,4,5,6,7,8,9。輸入格式兩個(gè)正整數(shù) n,sum。n w I2,sumw 12345。輸出格式輸出包括1 行，為字典序最小的那個(gè)答案。當(dāng)無(wú)解的時(shí)候，請(qǐng)什么也不輸出。輸入樣例4 16輸出樣例3 1 2 4( 1)編程思路。以題目示例來(lái)說(shuō)明。4 個(gè)數(shù) 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系數(shù) 1 、 3、 3、 1 正好四楊輝三角形的第4 行的值。因此，需要先求出楊輝三角形第n行的值，以便于最后總和的計(jì)算。生成 1n 的全排列，對(duì)生成的排列進(jìn)行判斷，看是否滿足和值等于輸入的sum， 如果找到的答案，置標(biāo)記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