信息學(xué)競賽典型例題程序匯集

1、信息學(xué)競賽復(fù)習(xí) 1. 斐波拉契數(shù)列(1000000以內(nèi)的數(shù)字) #i nclude“ stdio.h ” #i nclude“ stdlib.h ” void mai n() long fib仁 1,fib2=1,fib=0; printf(1000000以內(nèi)的數(shù)字：nn); prin tf(%dn%dn,fib1,fib2); while (fib1000000) fib=fib1+fib2; fib1=fib2; fib2=fib; prin tf( %d n, fib); system(pause); 2. 約瑟夫問題 (1) 約瑟夫問題數(shù)組 #i nclude stdio.h #in

2、clude stdlib.h #defi ne Len gth 100 void mai n() int i,j; int len; int n,m; int rema in; II輸入的總節(jié)點數(shù) /輸入的每次數(shù)幾個 II剩下的節(jié)點數(shù) int current;II當(dāng)前數(shù)到那個數(shù)字 int aLe ngth; for(i=0;i0) curre nt+; while(curre ntle n) curre nt-=le n; if(acurre nt=1) m+; if(m=n) acurre nt=O; remai n-; prin tf(%d, ”,curre nt); m=0; syste

3、m(pause); (2) 約瑟夫問題_數(shù)組環(huán) #i nclude stdio.h #in clude stdlib.h void mai n() /i循環(huán)len總數(shù)n每次數(shù)幾個 /cur 當(dāng)前是哪個 m 計數(shù)remain 剩下幾個 int a100; int i,le n,n; int cur,m,rema in; /int t1,t2; for(i=0;i0) cur=acur; m+; if(m=n_1) prin tf(%d, ”,acur); t仁 acur; t2=aacur; acur=aacur; remai n-; m=0; system(pause); (3) 約瑟夫問題_

4、鏈表 #i nclude stdio.h #in clude stdlib.h struct people int num; struct people *n ext; ; typedef struct people no de; node *create(i nt m) int i; n ode *h,*p1,*p2; h=p1=p2=(node *)malloc(sizeof( no de); h-num=1; for(i=1;in ext=p1; p1- num=i+1; p2=p1; p1- n ext=h; return h; node *fin dout (node *tp,i n

5、t n) int i; node *p; p=tp; for(i=1;in ext; return p; node *moveaway (node *tp) node *c,*p1,*p2; c=tp; p1=c- n ext; p2=p1- n ext; c-n ext=p2; prin tf(%d, ,p1- num); free(p1); return p2; void mai n() node *p; int len ,i, n; printf(”請輸入約瑟夫問題節(jié)點總數(shù)：); len=41; /sea nf(%d, printf(請輸入每次數(shù)的節(jié)點數(shù)字：); n=3;/scan f(

6、%d, p=create(le n); for(i=1;inum=1; for(i=1;in ext=p1; p1_prior=p2; p1- num=i+1; p2=p1; p1- n ext=h; h-prior=p1; return h; node *fin dout (node *tp,i nt n) int i; node *p; p=tp; for(i=1;in ext; return p; node *moveaway (node *tp) node *c,*p1,*p2; c=tp; p1=c-prior; p2=c- n ext; p1- n ext=p2; p2_prior

7、=p1; prin tf(%d, ,c- nu m); free(c); return p2; void mai n() node *p; int len ,i, n; printf(”請輸入約瑟夫問題節(jié)點總數(shù)：”)； le n=41;/sca nf(%d, printf(請輸入每次數(shù)的節(jié)點數(shù)字：); n=3;/sca nf(%d, p=create(le n); for(i=1;i=le n;i+) p=moveaway(fi ndout(p ,n); system(pause); 3. 數(shù)字7和5 (1)統(tǒng)計含有數(shù)字7,但不能被7整除的5位整數(shù)的個數(shù) #i nclude #i nclude

8、 void mai n() int sum=0;/統(tǒng)計個數(shù) int b;/ 起數(shù) int a 6; int have7; int j; int tempb; for(b=10000;b100000;b+) /分離數(shù)字到數(shù)組 tempb=b; for(j=0;j5;j+) a5-j=tempb-(tempb/10)*10; tempb=tempb/10; /判斷是否含7 have7=0; for(j=1;j0 sum+; prin tf(sum=%dn,sum); system(pause); (2)統(tǒng)計含有2個數(shù)字7但不能被7整除的5位整數(shù)的個數(shù) #i nclude #i nclude voi

9、d mai n() int sum=0;統(tǒng)計個數(shù) int b; 起數(shù) int a 6; int have7; int j; int tempb; for(b=10000;b100000;b+) /分離數(shù)字到數(shù)組 tempb=b; for(j=0;j5;j+) a5-j=tempb-(tempb/10)*10; tempb=tempb/10; /判斷是否含7 have7=0; for(j=1;j=5;j+) if(aj=7) have7+; if(have7=2 sum+; prin tf(sum=%dn,sum); system(pause); 問雞翁、 4. 百錢買百雞：雞翁一，值錢五；雞母

10、一，值錢三；雞雛三，值錢一；百錢買百雞, 雞母、雞雛各幾何？ (1) #inelude #i nclude void mai n() int i,j,k; for(i=1;i20;i+) for(j=1;j33;j+) k=100-i-j; if(i*15+j*9+k=300) printf(”雞翁 %d,雞母 %d,雞雛 %dn,i,j,k); system(pause); (2) #include #i nclude void mai n() int i,j,k; for(i=1;i20;i+) for(j=1;j33;j+) k=(100-i*5-j*3)*3; if(i+j+k=100

11、) printf(雞翁 %d,雞母 %d,雞雛 %dn,i,j,k); system(pause); 5. 逆序乘積式 int sum=0; (1)兩位數(shù)逆序乘積式 #i nclude void mai n() int a,b,c,d; int i,j,ir,jr,m, n; int arr5; int flag; for(i=10;i98;i+) arr1=a=i/10; arr2=b=i-a*10; for(j=i+1;j98;j+) arr3=c=j/10; arr4=d=j-c*10; /檢查有沒有相同數(shù)字 flag=0; for(m=1;m4;m+) for(n=m+1; n5;n+

12、) if(arrm=arr n) flag=1; break; /檢查完 /右側(cè)的逆序 ir=b*10+a; jr=d*10+c; if(flag=0 prin tf(%d:ti=%dt,j=%dt,ir=%dt,jr=%dn,sum,i,j,ir,jr); int sum=0; int a,b,c,d,e,f; (#)三位數(shù)逆序乘積式 #i nclude void mai n() int i,j,ir,jr,m, n; int arr7; int flag; for(i=100;i987;i+) arr1=a=i/100; arr2=b=i/10-a*10; arr3=c=i-a*100-b

13、*10; for(j=i+1;j987;j+) arr4=d=j/100; arr5=e=j/10-d*10; arr6=f=j-d*100-e*10; /檢查有沒有相同數(shù)字 flag=O; for(m=1;m6;m+) for(n=m+1; n7;n+) if(arrm=arr n) flag=1; break; / 檢查完 / 右側(cè)的逆序 ir=c*100+b*10+a; jr=f*100+e*10+d; if(flag=0 prin tf(%d:ti=%dt,j=%dt,ir=%dt,jr=%dn,sum,i,j,ir,jr); 6.雙和數(shù)組 (1 )普通解法 #i nclude voi

14、d mai n() int s; int a,b,c,d,e,f; int arr7; int flag,i,j; int sum=O; for (s=11;s=100;s+) prin tf(s=%d:n,s); for(a=1;a=s_2;a+) for(b=a+1;b=s-1;b+) for(d=a+1;d=s-2;d+) for(e=d+1;e=s-1;e+) c=s-a-b; f=s-d-e; /檢查是否有重復(fù)數(shù)字 arr1=a; arr2=b; arr3=c; arr4=d; arr5=e; arr6=f; if(ab for(i=1;i7;i+) for(j=i+1;j7;j+)

15、 if(arri=arrj) flag=1; if(arri0) /避免負(fù)數(shù) flag=1; /沒有重復(fù)的數(shù)字進(jìn)入且符合倒數(shù)條件 if(flag=O prin tf(s=%d;a=%d,b=%d,c=%d,d=%d,e=%d,f=%dn,s,a,b,c,d,e,f); prin tf(sum=%d,sum); (2)優(yōu)化后解法 #i nclude void mai n() int s; int a,b,c,d,e,f; int arr7; int flag,i,j; int sum=0; for (s=11;s=100;s+) prin tf(s=%d:n,s); for(a=1;a=s_2;

16、a+) for(b=a+1;b=s-1;b+) for(d=a+1;d=s-2;d+) for(e=d+1;e=s-1;e+) c=s-a-b; f=s-d-e; /檢查是否有重復(fù)數(shù)字 arr1=a; arr2=b; arr3=c; arr4=d; arr5=e; arr6=f; flag=0; for(i=1;i7;i+) for(j=i+1；j7;j+) if(arri=arrj) flag=1; if(arrib|ac|bc) flag=1; if(de|df|ef) flag=1; /沒有重復(fù)的數(shù)字進(jìn)入且符合倒數(shù)條件 if(flag=0 prin tf(s=%d;a=%d,b=%d,c

17、=%d,d=%d,e=%d,f=%dn,s,a,b,c,d,e,f); 7.八皇后問題 (1) 窮舉法 #i nclude #i nclude #in clude #defi ne N 8 /定義棋盤大小 void mai n(void) int num oftimes = 0; int count = 0; int aN + 1; int flag; int i1, i2, i3, i4, i5, i6, i7, i8, x, y, p; prin tf(%d皇后問題的窮舉法解決”,N); for (i1 = 1; i1 = N; i1+) a1 = i1; for (i2 = 1; i2

18、= N; i2+) a2 = i2; for (i3 = 1; i3 = N; i3+) a3 = i3; for (i4 = 1; i4 = N; i4+) a4 = i4; for (i5 = 1; i5 = N; i5+) a5 = i5; for (i6 = 1; i6 = N; i6+) a6 = i6; for (i7 = 1; i7 = N; i7+) a7 = i7; for (i8 = 1; i8 = N; i8+) a8 = i8; /檢測是否沖突 flag = 0; for (x = 1; x N; x+) for (y = x + 1; y = N; y+) if (a

19、x = ay | abs(ax - ay) =y - x) flag = 1; break; num oftimes+; if(flag=1) con ti nue; if (flag=O) coun t+; , coun t); prin tf(第4種解法: for (p = 1; p = N; p+) prin tf(%d, ap); prin tf(n); printf(” 共運仃計算4次門”，numoftimes); prin tf( 共找到d種方案n, count); system(pause); (2) 遞歸法 #i nclude stdio.h #defi ne N 8 /定義棋

20、盤大小 static int coun t,aN; / count記錄當(dāng)前已找到解的個數(shù) / aN記錄皇后的位置，表示第i行的皇后放在棋盤的第ai列 int num oftimes = 0; void recursive(i nt t) /嘗試第t行的放置方案 int i; int j; int sig n = 1; if (t = N + 1) /t = N + 1 /表示放下最后一個皇后，找到解法 coun t+; /* 第1種顯示方法*/ / t = N + 1 / 已經(jīng)得到一個解決方案 printf(”第4種解法：,count); /Literall.Text += string.Fo

21、rmat(”第0種解法:,count); for (i = 1; i = N; i+) prin tf(%d,ai); /Literal1.Text += stri ng.Format(0, ai); prin tf(n); /Literal1.Text += ; /* 第2種顯示方法 printf(第4種解法:n, count); for (i = 0; i N; i +) for (j = 0; j N; j +) if (j = ai) prin tf( ); else prin tf(* ); prin tf(n); prin tf(n); */ else /還沒有放下所有的皇后 fo

22、r (i = 1; i = N; i+) / 依次嘗試在第t行的第1列到 第N列放置 at = i; sig n = 1; for (j = 1; j = t - 1; j+) /測試皇后在第t行第at列時是否與前面已放置好的皇后相攻擊。 /aj =at時，兩皇后在同一列上； abs(t - j) = abs(aj - at)時，兩皇后在同一斜線上。 /兩種情況兩皇后都可相互攻擊，故不符合條件。設(shè)置sig n=0 /if (Math.Abs(t - j) = Math.Abs(aj - at) | (aj = at) if (abs(t - j) = abs(aj - at) | (aj =

23、at) sig n = 0; numo ftimes+; /如果沒有沖突，繼續(xù)嘗試 if (sig n = 1) recursive(t + 1); else / / 有沖突的方案丟棄! 也可以在此記錄 void mai n(void) 從第1行開始放置皇后 recursive。);/ printf(運行 畝:，numoftimes); system(pause); (3) 回溯法 #in clude #i nclude #in clude #defi ne N 8 void mai n() int num oftimes = 0; int count = 0;/ 解法的個數(shù)(計數(shù)器) int

24、 aN+1;/i,ai分別代表第i行和這行中皇后放置的列數(shù) int flag;/ 標(biāo)記0或1,0代表有沖突；1代表沒有沖突 int i,j;/ 循環(huán)變量 int m; m=1;am = 1;/ 從第1行開始第1行從第1列開始放置皇后 while (a1 = 1; i_) /檢查當(dāng)前行放置位置，與之前的所有行有沒有沖突 if (am = ai | abs(am - ai) = m - i) flag = 1; break; if (flag=0 printf(”第 4種解法：, coun t); for (i = 1; i N + 1; i+) prin tf(%d, ai); prin tf(

25、n); if (flag=0 退回上1行 am+;右移1列 printf(共運行計算 4次門”，numoftimes); printf(”共找到 d種方案 nn, count); system(pause); 8.橋本分?jǐn)?shù)式 (1) 窮舉法 #i nclude #i nclude /橋本分?jǐn)?shù)式求解 void mai n() int sum=0,r uncount; int i1,i2,i3,i4,i5,i6,i7,i8 ,i9; int flag; int a11; int m, n,j; int left,right,ab; for(i 仁1;i1=9;i1+) for(i2=1;i2=9;

26、i2+) for(i3=1;i3=9;i3+) for(i4=1;i4=9;i4+) for(i5=1;i5=9;i5+) for(i6=1;i6=9;i6+) for(i7=1;i7=9;i7+) for(i8=1;i8=9;i8+) for(i9=1;i9=9;i9+) runcoun t+; a1=i1; a2=i2; a3=i3; a4=i4; a5=i5; a6=i6; a7=i7; a8=i8; a9=i9; /檢查是否有重復(fù)數(shù)字 flag=O; for(m=1;m9;m+) for(n=m+1; n10 ;n+) if(am=a n) flag=1; /檢查重復(fù)完成 if(fla

27、g=0 right=i7*(i2*10+i3)*(i5*10+i6); if(left=right) sum+; prin tf(%d:%d/%d%d+%d/%d%d=%d/%d%dn,sum,i1,i2,i3,i4,i5,i6,i7,i8,i9); printf(”共進(jìn)行檢測 d次。n, runcount); system(pause); (2) 遞歸法 #i nclude stdio.h static int coun t,a1O; / count 記錄當(dāng)前已找到解的個數(shù) / a10 記錄 a1-a9 的數(shù)字 int num oftimes = 0; void recursive(i nt

28、 i) /嘗試第t位的數(shù)字 int j,k; int sig n; long m1,m2,m3; if (i = 9) if(a1a4) /符合基本條件 /1所有數(shù)字不重復(fù)出現(xiàn) /2所有數(shù)字已經(jīng)使用完 /3 a1a4，避免分?jǐn)?shù)式左邊的兩項交替出現(xiàn) /符合以上條件，才檢測分?jǐn)?shù)式是否成立 m仁a2*10+a3; m2=a 5 *10+a6; m3=a8*10+a9; if(a1*m2*m3+a4*m1*m3=a7*m1*m2) /找到一個符合條件的分?jǐn)?shù)式 coun t+; printf(找到第 d個：,count); prin tf(%d/%d%d+%d/%d%d=%d/%d%dn,a1,a2,a

29、3,a4,a5,a6,a7,a8, a9); else /i 9，沒有到最后一位數(shù)字 for(k=1;k=1;j-) if(ai=aj) sig n=0; break; /有重復(fù)的數(shù)字，終止測試 ai=aj if(sig n=1 void mai n(void) recursive。);/ 從第1行開始放置數(shù)字 printf(”運行 畝:，numoftimes); system(pause); (3) 回溯法 #i nclude stdio.h #in clude stdlib.h #in clude math.h #defi ne N 9 void mai n() int times=0;

30、int sum=0; int i,m; int aN+1; int flag; int a23,a56,a89; a1=1; m=1; while(a1=1;i-) if(am=ai) flag=1; if(flag=0 a56=a5*10+a 6; a89=a8*10+a9; if(a1a4 for(i=1;i=N;i+) prin tf(%d,ai); prin tf(n); if(flag=0 am+; prin tf(ntimes=%dn,times); prin tf(nsum=%dn,sum); 9.神奇的古尺：一個古尺，總長36寸，因年代久遠(yuǎn)，中間標(biāo)注的刻度只剩下8個，但是這 個

31、尺子還是可以一次性度量136之間的任意長度，請確定這8個刻度的位置。 (1)窮舉法-優(yōu)化 #i nclude #in elude void mai n() int testTimes=O; int a10;刻度數(shù)組 int b37;長度檢測數(shù)組 int i1,i2,i3,i4,i5,i6,i7,i8; int i,j; int flag,sig n; /頭尾 a0=0;a9=36; for(i 仁1;i1=28;i1+) a1=i1; for(i2=i1+1;i2=29;i2+) a2=i2; for(i3=i2+1;i3=30;i3+) a3=i3; for(i4=i3+1;i4=31;i4

32、+) a4=i4; for(i5=i4+1;i5=32;i5+) a5=i5; for(i6=i5+1;i6=33;i6+) a6=i6; for(i7=i6+1;i7=34;i7+) a7=i7; for(i8=i7+1;i8=35;i8+) a8=i8; /所有的不重復(fù) testTimes+; / / / / / / if(testTimes%100000=0) /輸出檢測到得位置，不是解 printf(”輸出檢測到得位置，不是解 ); for(i=1;i=8;i+) / / / / prin tf(%d,ai); prin tf(n); flag=0; for(i=1;i8;i+) fo

33、r(j=i+1;j=8;j+) if(ai=aj) flag=1; if(flag=0) /開始檢測所有的可能的刻度 for(i=1;i0;i-) for(j=i-1;j=0;j-) bai-aj=1; /檢測b數(shù)組是否全部=1 sig n=0; for(i=1;i=36;i+) if(bi=0) sig n=1; if(sig n=0) /輸出解 prin tf(找到的可能刻度為); for(i=1;i=8;i+) prin tf(n); printf(程序共檢測了 d種組合 n,testTimes); system(pause); (2)回溯法-優(yōu)化 #i nclude #i nclude

34、 #defi ne LEN 36 #defi ne N 7 void mai n() int testTimes=0,sum=0; int aN+2;刻度數(shù)組 int bLEN+1;長度檢測數(shù)組 int i,j;循環(huán)變量 int m,q; int flag,sig n; /頭尾 a0=0;aN+1=LEN;m=1;a1=1; while(a1=22) / /system(pause); /pri ntf(i=%d,a%d=%dn,i,i,ai); /for(i=1;i=8;i+) / /prin tf(%d,ai); /prin tf(n); / / if(m=N) for(i=1;i0;i-

35、) for(j=i-1;j=0;j-) bai-aj=1; /檢測b數(shù)組是否全部=1 sig n=0; for(i=1;i=LEN;i+) if(bi=0) sig n=1; break; if(sig n=0) sum+; /輸出解 printf(”找到的可能刻度為); for(i=1;i=N;i+) prin tf(%d,ai); prin tf(n); /不用檢測重復(fù)的值 / 所以不用加 flag=0 if(flag=0 am+; printf(程序共檢測了 c種組合 n,testTimes); printf(”共有 d#合條件 n”,sum); system(pause); 10. 別

36、出心裁的情侶拍照：8對情侶，參加聚會后拍照，主持人要求如下：每對情侶不得相 鄰，每對情侶都是男左女右排隊，編號為 1的情侶之間有1個人，編號為2的情侶之間有 2個人，依次類推，編號為 8的情侶之間有8個人 分析： a數(shù)組代表位置a1-a8 /數(shù)組的值表示對應(yīng)的人 a仁2表示第1個位置是編號為2個男生 / 4對情侶編號為1-8 1-4 為男生，5-8為女生 1和5為1對 2和6為1對 3和7為1對 4和8為1對 (1) 回溯法-優(yōu)化 #i nclude #i nclude #in clude #defi ne N 8 void mai n() int testTimes=0; int sum=0

37、; int a2*N+1; int i;循環(huán)變量 int flag; int m; 回溯變量 int lovers;/統(tǒng)計已經(jīng)安排的情侶人數(shù)，當(dāng)lovers=2*N時，全部安排好 for(i=1;i=2*N;i+) ai=0; m=1;a1=1;lovers=1; /循環(huán)條件a12*N+1可以優(yōu)化為a1N+1 while(a1N+1) testTimes+; flag=O; ,lovers,testTimes,m); /prin tf(lovers=%d;testTimes=%d;m=%d; 測試: /for(i=1;i0;i-) /不重復(fù) if(am=ai) flag=1; break; /

38、 判斷 1對情侶是否可以排好 /m+am+1，女生位置是否超出范圍 am+am+1=0 ，女生位置是否已經(jīng)有人？ if(flag=0 lovers+;/ 安排一個 else flag=1; /所有情侶已經(jīng)安排好，并且沒有出錯 if(flag=0 for(i=1;i=2*N;i+) prin tf(n); /沒有出錯，但是情侶沒有安排完lovers2*N if(flag=O lovers-;/取消一個 am=0; lovers-;/取消一個 /找到當(dāng)前位置左邊的第1男生 /男生的標(biāo)記N); /改動am之前 if( m+am+1=2*N lovers-;/取消一個 am+; printf(程序共檢

39、測了 c種組合 n,testTimes); printf( 共找到曲申組合符合要求n,sum); system(pause); (2) 回溯法 #i nclude #i nclude #in clude #defi ne N 8 void mai n() int testTimes=0; int sum=0; int a2*N+1; int i;循環(huán)變量 int flag; int m; 回溯變量 m=1;a1=1; /循環(huán)條件a12*N+1可以優(yōu)化為a1N+1 while(a1N+1) testTimes+; /if(testTimes%10000000=0) / /prin tf(test

40、Times=%dn,testTimes); /for(i=1;i0;i-) /不重復(fù) if(am=ai) flag=1; break; /男左女右 if(abs(ai-am)=N break; /情侶間隔的人數(shù)等于編號數(shù) if(abs(ai-am)=N break; if(flag=0 for(i=1;i=2*N;i+) prin tf(%d,ai); prin tf(n); if(flag=0 am+; printf(程序共檢測了 d種組合 n,testTimes); printf( 共找到4種組合符合要求n,sum); system(pause); 11. 四大湖泊：我國有4大淡水湖。A說

41、：洞庭湖最大，洪澤最小。鄱陽湖第三。B說： 洪澤湖最大，洞庭湖最小，鄱陽湖第二。太湖第三。C說：洪澤湖最小，洞庭湖第三。D 說：鄱陽湖最大，太湖最小，洪澤湖第二，洞庭湖第三。4個人每人僅答對了一個，請你 編程給出4個湖從大到小的順序。 (1) #inelude #i nclude void mai n() int a,b,c,d; for(a=1;a=4;a+) for(b=1;b=4;b+) for(c=1;c=4;c+) for(d=1;d=4;d+) if(a+b+c+d=10 system(pause); (2)回溯法 #i nclude #i nclude void mai n()

42、int j; int arr5; int i=1; int flag; int a,b,c,d; arr1=1; while(arri0;j-) if(arrj=a 叫i) flag=1; break; a=arr1; b=arr2; c=arr3; d=arr4; /輸出 if(flag=0 if(flag=0 arri+; system(pause); (3) 優(yōu)化 #i nclude #i nclude void mai n() int a,b,c,d; for(a=1;a=4;a+) for(b=1;b=4;b+) for(c=1;c=4;c+) for(d=1;d=4;d+) a+b

43、+c+d=10 if(a!=b system(pause); 12. 完美綜合式-回溯法 #i nclude #i nclude void mai n() int run times=0; int sum=0; int flag; int a11; int m, n,i,j; int left,right,ab; /初始條件設(shè)定 i=1; a1=1; while(ai= 1; j-) /檢查當(dāng)前行放置位置，與之前的所有行有沒有沖突 if (ai = aj) flag = 1; break; /檢查重復(fù)完成 if(flag=0 for(j=1;j=a2;j+) ab=ab*a1; left=(a

44、5*10+a6)*ab+(a3*10+a4); right=(a7*10+a8)*a9*(a 5 *10+a 6); if(left=right) /輸出 sum+; prin tf(%d:%dA%d+%d%d/%d%d-%d%d*%d=0n,sum,a1,a2,a3,a4,a5,a6,a 7,a8,a9); if(flag=0檢測下一個數(shù)字，一直到 9為止 prin tf(共運行計算 4次門，run times); printf(”共找到 d種方案 nn, sum); system(pause); 13. 裝錯信封：/某人給5個朋友寫信，同時寫了 5個朋友的信封問每個信封和信都不相符的 情況

45、有多少？ (1)窮舉法 #i nclude #i nclude #defi ne N 5 void mai n() int testTimes=0; int sum=0; int aN+1;信封數(shù)組a1=1，對應(yīng) int i1,i2,i3,i4, i5; int i,j; int flag; for(i 仁1;i1=N;i1+) a1=i1; for(i2=1;i2=N;i2+) a2=i2; for(i3=1;i3=N;i3+) a3=i3; for(i4=1;i4=N;i4+) a4=i4; for(i5=1;i5=N;i5+) a5=i5; /所有的不重復(fù) testTimes+; fla

46、g=O; for(i=1;iN;i+) for(j=i+1;j=N;j+) if(ai=aj) flag=1; if(flag=0 /輸出解 for(i=1;i=N;i+) prin tf(%d,ai); prin tf(n); /printf(程序共檢測了 d種組合 n”,testTimes); printf(共找到4種組合符合要求n,sum); system(pause); (2)回溯法 #i nclude #i nclude #defi ne N 5 void mai n() int testTimes=0; int sum=0; int aN+1;/信封數(shù)組 a1=1，對應(yīng) int i

47、,j;/循環(huán)變量 int flag; int m;/回溯變量 m=1;a1=1; while(a10;i-) if(ai=am) flag=1; break; /增加條件，減少搜索范圍 for(i=m;i0;i-) if(ai=i) flag=1; break; if(flag=0 for(i=1;i=N;i+) prin tf(%d,ai); prin tf(n); if(flag=0 am+; printf(程序共檢測了 c種組合 n,testTimes); printf(共找到曲申組合符合要求n,sum); system(pause); 14. 漢諾塔 (1 )漢諾塔移動步驟 #i nc

48、lude #i nclude void move(char x,char y) prin tf(%c-%c n,x,y); II將n個盤從a座借助b座,移到c座 void hanoi(int n, char a,char b,char c) if(n=1) move(a,c); else hanoi(n-1,a,c,b); move(a,c); han oi( n-1,b,a,c); int mai n() int m=4; han oi(m,1,2,3); system(pause); (2)漢諾塔移動次數(shù)計算 #i nclude #i nclude II將n個盤從a座借助b座,移到c座 d

49、ouble t(i nt m) double s; if(m=1) s=1; else s=2*t(m-1)+1; return s; int mai n() int m=64; prin tf(%.Of,t(m); system(pause); 15. 水手分椰子：5個水手帶著1只猴子來到一座荒島，見島上有大量椰子，他們便把這些 椰子平均分成5堆。夜深人靜，一個水手偷偷起來拿走了一堆椰子，把剩下的椰子又平均分 成5堆，結(jié)果多出一只椰子丟給猴子吃掉了，過了一會兒，另一個水手也偷偷起來，拿走了 一堆椰子后，再把剩下的椰子平均分成5堆，結(jié)果還是多了一只，丟給猴子吃了。就這個多 事的月黑風(fēng)高的夜晚，

50、5個水手都偷偷藏起一堆，重分了椰子，每次都多出一只椰子讓猴子 占了便宜。第二天一早，島上依然平均堆放著5堆椰子。問：原先的椰子最少要有多少只？ #i nclude #i nclude #in clude #defi ne N 5 void mai n() int times=0; int i=0; double y,k,x; y=k=1; while(i6) times+; i+; /printf(”第4次遞推，原有 %8.0f 個！ n,i,y); y=(y*5+1)/4; if(y!=floor(y) y=k+; i=0; /pri ntf( try agai nn); printf(這堆

51、椰子原有%6.0f個！ ”,y); printf(”共計算 d次！ ”,times); system(pause); 16. 整數(shù)劃分：正整數(shù)可以分成若干個正整數(shù)之和。如：2: 1+1; 23: 1+1+1; 1+2; 3 4: 1+1+1+1; 1+1+2; 1+3; 2+2; 4 #i nclude #i nclude #defi ne N 5 void mai n() int i,j; int temp1,temp2; int m; int quantity;/u是整數(shù)劃分式的個數(shù)，如4: quantity=5 int newI;/ 增加的新項目編號 static int a80021;

52、 /初始化，全部置為 0 for(i=0;i=800;i+) for(j=0;j=21;j+) aij=0; qua ntity=2; a11=1; a12=1; a21=2; / for(m=3;m=N;m+) /從前一個加1 for(i=1;i=qua ntity;i+) temp1=ai1; ai1=1; j=2; while(aij!=0) temp2=aij; aij=temp1; temp1=temp2; j+; aij=temp1; / 增加的部分劃分式 n ewl=qua ntity; for(i=1;i=qua ntity;i+) if(ai2ai3) n ewl+; a n

53、ewl1=ai2+1; j=3; while(aij!=O) a newlj-1=aij; j+; / n ewI+; a newI1=m; qua ntity=n ewI; for(i=1;i0) prin tf(+%d,aij); j+; prin tf(n); prin tf(n); system(pause); 17. 最長非降子序列 (1)遞推法 #in clude #in clude #defi ne N 10 void mai n() int aN=47,36,52,46,45,28,46,69,14,42; int bN; int max,le n; int i,j; bN-1

54、=1; le n=1; for(i=N-2;i=0;i-) max=0; for(j=i+1;j=N-1;j+) if(aimax) max=bj; bi=max+1; if(bile n) len=bi; for(i=0;i=N-1;i+) prin tf(%3d ”,ai); prin tf(n); for(i=0;i=N-1;i+) prin tf(%3d ”,bi); prin tf(n最長序列=%3d n,le n); j=le n; for(i=0;i=N-1;i+) if(bi=j) prin tf(%3d ”,ai); j-; prin tf(n); system(pause)

55、; (2)遞歸法 #in clude #i nclude int a10=47,36,52,46,45,28,46,69,14,42; int n=10; int b(i nt i) int j,retur nValue; int ma x; int temp; if(i=n-1) returnValue=1; else max=0; for(j=i+1;j=n _1;j+) temp=b(j); if(aimax) max=temp; retur nV alue=max+1; return returnValue; void mai n() int i,le n,j; int temp; f

56、or(i=0;i n;i+) prin tf(%3d ”,ai); prin tf(n); len=0; for(i=0;ile n) len=temp; prin tf(n最長序列=%3d n,le n); j=le n; for(i=0;i n;i+) if(b(i)=j) prin tf(%3d ”,ai); j-; prin tf(n); system(pause); 18. 三角形最優(yōu)路徑 (1 )三角形最大路徑 #i nclude #i nclude #in clude void mai n() int n,i,j,t; int a5050,b5050; char LorR5050

57、; sran d(i nt)time(O); n=5; for(i=1;i=n ;i+) for(j=1;j=36-2*i;j+) printf(); for(j=1;j=i;j+) aij=ra nd()%10; prin tf(%4d,aij); prin tf(n); n); printf(”請在以上點數(shù)值三角形中從頂開始，每步可左斜或右斜 printf(尋找一條數(shù)字和最大的路徑n); /最下面一層 for(i=1;i=1;i-) for(j=1；j=i;j+) if(bi+1jbi+1j+1) bij=aij+bi+1j+1; LorRij=R; else bij=aij+bi+1j;

58、 LorRij=L; n “); printf(” 輸出3個數(shù)組的值 for(i=1;i=n ;i+) for(j=1;j=36-2*i;j+) printf(); for(j=1;j=i;j+) prin tf(%4d,aij); prin tf(n); for(i=1;i=n ;i+) for(j=1;j=36-2*i;j+) printf(); for(j=1;j=i;j+) prin tf(%4d,bij); prin tf(n); for(i=1;i=n ;i+) for(j=1;j=36-2*i;j+) printf(” ); for(j=1;j=i;j+) prin tf(%4c

59、丄 orRij); prin tf(n); printf(最大路徑和為 %dn,b11); printf(最大路徑為 %d,a11); j=1; for(i=2;i=n ;i+) if(LorRi-1j=R) prin tf(-R-%d,aij+1); j+; else prin tf(-L-%d,aij); prin tf(n); system(pause); (2 )三角形最小路徑 #i nclude #i nclude #in clude void mai n() int n,i,j,t; int a5050,b5050; char stm5050; sran d(i nt)time(O); n=5; for(i=1;i=n ;i+) for(j=1;j=36-2*i;j+) printf(” ”); for(j=1；j=i;j+) aij=ra nd()%100; prin tf(%4d,aij); prin tf(n); n); printf(”請在以上點數(shù)值三角形中從頂開始，每步可左斜或右斜 printf(”尋找一條數(shù)字和最小的路徑n); /最下面一層 for(i=1;i=1;i-) for(j=1;jbi+1j+1) bi