程序設(shè)計(jì)培訓(xùn)講義3：枚舉算法

1、程序設(shè)計(jì)講義之三 枚舉算法1枚舉法也稱(chēng)窮舉法、窮舉搜索法算法思想： 對(duì)所有可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問(wèn)題的解。 算法特點(diǎn)： 算法簡(jiǎn)單，但執(zhí)行效率低。因此枚舉法的關(guān)鍵在于提高編程效率。2例1、求水仙花數(shù)/ 程序1：對(duì)數(shù)循環(huán)#include void main()int i,a,b,c;for (i=100; i=999; i+)a=i/100;b=i/10%10;c=i%10;if (a*a*a+b*b*b+c*c*c=i)printf(%dn,i);3/ 程序2：對(duì)數(shù)的各位數(shù)字循環(huán)#include void main( )int n,a

2、,b,c;for (a=1; a=9;a+)for (b=0; b=9; b+)for (c=0; c=9; c+)n=a*100+b*10+c;if (n=a*a*a+b*b*b+c*c*c)printf(%dn,n); 4例2、百雞百錢(qián)問(wèn)題設(shè)母雞每只5元，公雞每只3元，小雞1元3只?，F(xiàn)用100元買(mǎi)100只雞，求出所有可能的解。算法分析：設(shè)母雞、公雞、小雞分別為x、y、z只，則應(yīng)滿(mǎn)足下面2個(gè)條件：x+y+z=1005x+3y+z/3=100 對(duì)于此類(lèi)實(shí)際問(wèn)題，還需考慮x,y,z的取值范圍： 0= x =1000= y =1000= z =100 5/ 程序1：有問(wèn)題的程序#include v

3、oid main()int x,y,z;for (x=0; x=100;x+)for (y=0; y=100; y+) for (z=0; z=100; z+) if ( x+y+z=100 & 5*x+3*y+z/3=100 )printf(%d,%d,%dn,x,y,z); 思考：1、上面的程序能否輸出所有可能的解？ 2、上面的程序是否輸出了錯(cuò)誤的解？ 3、上面的程序的時(shí)間復(fù)雜度？6/ 程序2：正確的程序#include void main()int x,y,z;for (x=0; x=100;x+)for (y=0; y=100; y+) for (z=0; z=100; z+) if

4、( z%3=0 & x+y+z=100 & 5*x+3*y+z/3=100 )printf(%d,%d,%dn,x,y,z); 問(wèn)題：上面程序的執(zhí)行速度太慢，如何解決？7/ 程序3：改進(jìn)后的程序#include void main()int x,y,z;for (x=0; x=100;x+)for (y=0; y=100; y+)z=100-x-y;if (z%3=0 & 5*x+3*y+z/3=100)printf(%d,%d,%dn,x,y,z); 問(wèn)題：上面程序的執(zhí)行速度還可以加快，如何修改？8/ 程序4：對(duì)程序3改進(jìn)后的程序#include void main()int x,y,z;f

5、or (x=0; x=20;x+)for (y=0; y=99; y+)z=100-x-y;if ( z%3=0 & 5*x+3*y+z/3=100)printf(%d,%d,%dn,x,y,z); 思考：是否可以將對(duì)y的循環(huán)改成對(duì)z的循環(huán)？9/ 程序5：對(duì)程序3的另一種改進(jìn)#include void main()int x,y,z;for (x=0; x=20;x+)for (z=0; z=99; z=z+3)y=100-x-z;if ( 5*x+3*y+z/3=100)printf(%d,%d,%dn,x,y,z); 思考：上面程序的存在什么問(wèn)題，為什么會(huì)出現(xiàn)問(wèn)題？10例3、兩個(gè)乒乓球隊(duì)進(jìn)

6、行比賽，各出3人。甲隊(duì)為A、B、C三人，乙隊(duì)為X、Y、Z三人。有人向隊(duì)員打聽(tīng)比賽的名單，A說(shuō)他不和X比， C說(shuō)他不和X、Z比，編程找出三對(duì)比賽的名單。例4、現(xiàn)有紅、黃、黑、白色球各一個(gè)，放置在一個(gè)內(nèi)編號(hào)1、2、3、4四個(gè)盒子中，每個(gè)盒子放置一球，它們的位置未知。小李、小張和小劉的猜測(cè)如下：小李認(rèn)為黑球編號(hào)1，黃球編號(hào)2；小張認(rèn)為黑球編號(hào)2，白球編號(hào)3；小劉認(rèn)為紅球編號(hào)2，白球編號(hào)4。結(jié)果表明他們各猜對(duì)了一半。根據(jù)他們的猜測(cè)確定四個(gè)色球在哪個(gè)盒子？ 11/例3：兩個(gè)乒乓球隊(duì)比賽#include void main( )char A,B,C;for (A=X; A=Z; A+)for (B=X;

7、B=Z; B+) for (C=X; C=Z;C+)if ( A!=X & C!=X & C!=Z & A!=B & A!=C & B!=C )printf(A=%c,B=%c,C=%cn,A,B,C); 12例4算法分析：關(guān)鍵是如何表示“每個(gè)人只說(shuō)對(duì)了一個(gè)”，也就是說(shuō)“一個(gè)表達(dá)式為真，另一個(gè)為假”方法1 相與為假，相或?yàn)檎娣椒? 兩個(gè)關(guān)系表達(dá)式的和為1方法2 兩個(gè)關(guān)系表達(dá)式不相等13/程序：紅、黃、黑、白色球#include void main( ) int a,b,c,d; for (a=1;a=4;a+) for (b=1; b=4; b+) for (c=1; c=4; c+) d=1

8、0-a-b-c; if ( (c=1)!=(b=2) & (c=2)!=(d=3) & (a=2)!=(d=4) & a!=b & a!=c & a!=d & b!=c & b!=d & c!=d ) printf(%d,%d,%d,%dn,a,b,c,d); 14例5、兩求邊長(zhǎng)不大于20的所有直角三角形。#include void main()int a,b,c;for (a=1; a20; a+)for (b=1; b20; b+)for (c=1; c=20; c+) if (a*a+b*b=c*c) printf(a=%d,b=%d,c=%dn,a,b,c);思考：1、上面程序是否輸出

9、了多余的解？ 2、如何減少上面程序種循環(huán)的次數(shù)？ 15/改進(jìn)后的程序#include void main( )int a,b,c;for (a=1; a20; a+)for (b=a; b20; b+)for (c=b; c=20; c+)if (a*a+b*b=c*c) printf(a=%d,b=%d,c=%dn,a,b,c);16練習(xí)題1 在1500中，找出能同時(shí)滿(mǎn)足用3除余2，用5除余3，用7除余2的所有整數(shù) 。練習(xí)題2 如果一個(gè)數(shù)從左邊讀和右邊讀都是同一個(gè)數(shù)，就稱(chēng)為回文數(shù)，例如686就是一個(gè)回文數(shù)。編程求1000以?xún)?nèi)所有的既是回文數(shù)同時(shí)又是素?cái)?shù)的自然數(shù)。 練習(xí)題3 試找出6個(gè)小于16

10、0而成等差數(shù)列的素?cái)?shù)。 17/練習(xí)題1：如何改進(jìn)？#include void main()int n;for (n=1; n=500; n+)if (n%3=2 & n%5=3 &n%7=2) printf(%10d,n); 改進(jìn)后#include void main()int n;for (n=2; n=500; n+=7)if (n%3=2 & n%5=3 ) printf(%10d,n); 18#include int huiwen(int n) / 判斷回文數(shù)int s=0,x=n;while ( x)s=s*10+x%10; x/=10; return s=n; int sushu(

11、int n) / 判斷素?cái)?shù)int i;for (i=2; in; i+)if (n%i=0) return 0;return 1; void main( ) /主函數(shù) int n; for (n=2; n=1000; n+) if ( huiwen(n) & sushu(n) ) printf(%10d,n); /練習(xí)題2：設(shè)計(jì)判斷回文數(shù)和素?cái)?shù)的函數(shù)19/練習(xí)題3：共4個(gè)函數(shù)（顯示、素?cái)?shù)、計(jì)算、主函數(shù)）#include void show(int a ) / 顯示數(shù)組aint i;for (i=0; i6; i+)printf(%10d,ai);printf(n);int sushu(int

12、n) /判斷n是否是素?cái)?shù)int i;for (i=2; in; i+)if (n%i=0) return 0;return n; 20/ a1和a2為等差數(shù)列中的前2個(gè)數(shù)/根據(jù)a1和a2來(lái)計(jì)算等差數(shù)列中的后4個(gè)數(shù)/如果后4個(gè)數(shù)都是素?cái)?shù)，則顯示void jisuan(int a ,int a1,int a2)int i;a0=a1;a1=a2;for (i=2;i160 | !sushu(ai) ) break; if (i=6) show(a); 21/主函數(shù)void main()int a6,a1,a2,i,j;for (i=2; i160; i+)if ( a1=sushu(i) ) /第

13、1個(gè)素?cái)?shù)for (j=i+1;j160; j+)if (a2=sushu(j) ) /第2個(gè)素?cái)?shù)jisuan(a,a1,a2); 22/練習(xí)題3的另一種解法：/設(shè)級(jí)數(shù)為：n，n-d，n-2d，n-3d，n-4d，n-5d。/若這個(gè)數(shù)全為素?cái)?shù)，則為要求的解。/這里d、n均是要尋找的，d最大可為33。#include int sushu(int n) /判斷n是否是素?cái)?shù)int i;for (i=2; in; i+)if (n%i=0) return 0;return 1; 23#include void main( ) int n,d; for (d=1;d=6; n-) if ( n-5*d1

14、& sushu(n) & sushu(n-d) & sushu(n-2*d) & sushu(n-3*d)& sushu(n-4*d) & sushu(n-5*d) ) printf(%d,%d,%d,%d,%d,%dn, n,n-d,n-2*d,n-3*d,n-4*d,n-5*d);24練習(xí)題4 已知一個(gè)正整數(shù)的個(gè)位數(shù)為7，將7移到該數(shù)的首位，其它數(shù)字順序不變，則得到的新數(shù)恰好是原數(shù)的7倍，編程找出滿(mǎn)足上述要求的最小自然數(shù)。練習(xí)題5 在純粹素?cái)?shù)是這樣定義的：一個(gè)素?cái)?shù)，去掉最高位，剩下的數(shù)仍為素?cái)?shù)，再去掉剩下的數(shù)的最高位，余下的數(shù)還是素?cái)?shù)。這樣下去一直到最后剩下的個(gè)位數(shù)也還是素?cái)?shù)。求出所有小于

15、3000的四位的純粹素?cái)?shù)。25/練習(xí)題4：無(wú)解#include int f(int n)int k,t=n;k=n%10; while ( t9 )k=k*10; t=t/10; return k+n/10; void main( )int i=7;while ( f(i)!=7*i )i=i+10;printf(%d,%dn,i,f(i) );26/練習(xí)題5：共3個(gè)函數(shù)（素?cái)?shù)、計(jì)算、主函數(shù)）#include int sushu(int n) /判斷n是否是素?cái)?shù)for (int i=2; in; i+)if (n%i=0) return 0;return 1; int jisuan(int x

16、) /判斷x是否滿(mǎn)足條件int i,t=1000;for (i=1;i=3; i+)if ( !sushu(x) ) return 0; x=x%t; t=t/10;return 1;27/練習(xí)題5的主函數(shù)void main()int i;for (i=1001; i3000; i=i+2)if ( jisuan(i) )printf(%10d,i);28練習(xí)題6 一個(gè)自然數(shù)，若它的素因數(shù)至少是兩重的（相同的素因數(shù)至少個(gè)數(shù)為二個(gè)，如：36=2*2*3*3），則稱(chēng)該數(shù)為“漂亮數(shù)”。若相鄰的兩個(gè)自然數(shù)都是“漂亮數(shù)”，就稱(chēng)它們?yōu)椤皩\生漂亮數(shù)”，例如8和9就是一對(duì)“孿生漂亮數(shù)”。編程再找出一對(duì)“孿生漂

17、亮數(shù)”。練習(xí)題7 若某個(gè)自然數(shù)的所有小于自身的因數(shù)之和恰好等于其自身，則該自然數(shù)稱(chēng)為一個(gè)完全數(shù)。例如：6是一個(gè)完全數(shù)，6=1+2+3。編程找出三個(gè)最小的完全數(shù)。 29/練習(xí)題6：漂亮數(shù)對(duì)#include int f(int n) /判斷n是否是為“漂亮數(shù)”int i,bz1=0,bz2;for (i=2; n1 ;i+)bz2=0;while (n%i=0 )n=n/i; bz2+; bz1+; if ( bz2=1) return 0; if (bz10) return 1; else return 0;30/練習(xí)題6：主函數(shù)void main()int a=2,i=0;while (i2)

18、if ( f(a) & f(a+1) )printf(%d,%dn,a,a+1); i+; a+;31/練習(xí)題7：三個(gè)最小的完全數(shù)#include int f(int n)int i,s=0;for (i=1; in; i+)if ( n%i=0 ) s=s+i;return s; void main()int a=6,i=0;while (i3)if ( f(a)=a )printf(%dn,a); i+; a+;32例6、求出方程 Xn+Yn = Sn+tn 的最小整數(shù)(使方程兩邊的數(shù)值最小)解。其中x，y，s，t，n 均為整數(shù)，當(dāng)給出n之后，求出滿(mǎn)足方程的最小整數(shù)解，且xt，xs。例如n

19、=2時(shí)，滿(mǎn)足方程的最小整數(shù)解為：52+52= 12+72=50 算法分析：由于不能確定x、y、s、t的取值范圍，也不能對(duì)x和y 設(shè)計(jì)下面這樣的循環(huán)（x不可能自增）：for (x=1; ; x+) for (y=1; ; y+) 所以，對(duì)方程兩邊的數(shù)值和進(jìn)行循環(huán)。 33#include int f(int x,int n)int s=1,i;for (i=1; i=n; i+)s=s*x;return s; void main()int n,x,y,t,s,m;scanf(%d,&n); 34for (m=1; ;m+) for (x=1;f(x,n)m; x+) for (y=1 ; f(y,

20、n)m; y+) if ( f(x,n)+f(y,n)=m) for (t=2; f(t,n)m; t+) for (s=2; f(s,n)m; s+)if ( f(t,n)+f(s,n)=m & x!=t & x!=s & y!=t) printf(%d,%d,%d,%dn,x,y,t,s);goto abc; abc: ;35練習(xí)題8運(yùn)動(dòng)會(huì)連續(xù)開(kāi)了n天，一共發(fā)了m枚獎(jiǎng)?wù)拢谝惶彀l(fā)枚并剩下(m-1)枚的1/7，第二天發(fā)枚并剩下的1/7，以后每天按此規(guī)律發(fā)獎(jiǎng)?wù)拢谧詈笠惶旒吹趎天發(fā)了剩下的n枚獎(jiǎng)?wù)?。?wèn)運(yùn)動(dòng)會(huì)開(kāi)了多少天？一共發(fā)了幾枚獎(jiǎng)?wù)?？練?xí)題9 五個(gè)學(xué)生A、B、C、D、E參加某一項(xiàng)比賽。甲、乙

21、兩人在猜測(cè)比賽的結(jié)果。甲猜的名次順序?yàn)锳、B、C、D、E，結(jié)果沒(méi)有猜中任何一個(gè)學(xué)生的名次，也沒(méi)有猜中任何一對(duì)相鄰名次（所謂一對(duì)相鄰名次，是指其中一對(duì)選手在名次上鄰接。例如與，或者與等）。乙猜的名次順序?yàn)镈、A、E、C、B，結(jié)果猜中了兩個(gè)學(xué)生的名次，并猜對(duì)了兩對(duì)學(xué)生名次是相鄰的。問(wèn)比賽結(jié)果如何？36/練習(xí)題8 ：運(yùn)動(dòng)會(huì)獎(jiǎng)?wù)?includevoid main( )int x=0,m,n,bz;do x+; m=7*x+1; n=1; bz=1; while ( mn & bz) m=m-n; if (m % 7=0) m=m/7*6; else bz=0; n+; while ( ! bz ) ;

22、printf(n=%d,m=%dn,n,7*x+1);37練習(xí)題9 算法分析：設(shè)五名選手A、B、C、D、E 分別用變量a、b、c、d、e來(lái)表示。通過(guò)對(duì)關(guān)系表達(dá)式相加的結(jié)果來(lái)表示猜測(cè)比賽的結(jié)果。#includevoid main()int a,b,c,d,e,b1,b2,b3,b4,b5,x1,x2,x3,x4;for (a=1;a=5;a+)for (b=1; b=5; b+)for (c=1; c=5; c+)for (d=1; d0 ) printf(a=%d,b=%d,c=%d,a,b,c); printf(d=%d,e=%dn, d,e); 39例7：0-1背包問(wèn)題 有不同價(jià)值、不同重

23、量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過(guò)指定的限制重量，但選中物品的價(jià)值之和最大。例如：設(shè)限制重量為7，現(xiàn)有4件物品，它們的重量和價(jià)值見(jiàn)下表，問(wèn)如何物品的價(jià)值之和最大？物品0123重量5321價(jià)值443140 0-1背包問(wèn)題有很多解法：遞歸算法（見(jiàn)程序設(shè)計(jì)培訓(xùn)講義4）、動(dòng)態(tài)規(guī)劃算法（程序設(shè)計(jì)培訓(xùn)講義9） ，下面是枚舉法的解題過(guò)程：枚舉算法（判斷所有可能的解）每種物品都有2種選擇：選與不選。設(shè)選擇物品用1表示，不選擇用0表示；則所有可能的解空間為：從100000 到 111 111，每個(gè)可能的解有n位。計(jì)算出每個(gè)可能的解的價(jià)值，即可得出最大值。下面程序中的

24、數(shù)組bN用來(lái)循環(huán)所有的解，aN用來(lái)表示已求出的最大值的解空間(選擇與不選擇)，m表示已求出的最大值。41#include# include #define N100float wN,vN,max_w,max_v=0;/ 存放每種物品的重量、價(jià)值、限制重量與最大價(jià)值int n,aN,bN;/存放物品種數(shù)、每種物品選擇標(biāo)記（1:選 0:不選）int pow(int k) /計(jì)算所有可能的解的個(gè)數(shù)2nint i,s=1;for (i=1; i=k; i+) s=s*2;return s; 42void input( ) int i;printf(輸入物品種數(shù)n);scanf(%d,&n);print

25、f(輸入各物品的重量和價(jià)值n);for (i=0;in;i+)scanf(%f%f,&wi,&vi);printf(輸入限制重量n); scanf(%f,&max_w);43void f( ) /計(jì)算解對(duì)應(yīng)的價(jià)值int i;float weight=0,value=0;for (i=0; in; i+)if ( bi=1 ) weight+=wi;value+=vi; if ( weightmax_v )max_v=value; /保存最大解的價(jià)值for (i=0; in; i+ ) /保存最大解的物品號(hào)ai=bi;44void max( )int i,j,t;for (i=0; i=0; j

26、-) /計(jì)算對(duì)應(yīng)物品 bj=t%2; t=t/2; f( ); void main( )input( );max();for (int i=0;in;i+)if (ai) printf(%4d,i+1);printf(n最大價(jià)值為%.2fn,max_v);45例8：卡車(chē)更新問(wèn)題 某人購(gòu)置了一輛新卡車(chē), 從事個(gè)體運(yùn)輸業(yè)務(wù). 給定以下各有關(guān)數(shù)據(jù)（數(shù)據(jù)為實(shí)型, 單位為萬(wàn)元 ）: rt, t=1,2,.,k, 表示已使用過(guò) t 年的卡車(chē), 再工作一年所得的運(yùn)費(fèi), 它 隨 t 的增加而減少, k (k20) 年后卡車(chē)已無(wú)使用價(jià)值。 ut, t=1,.,k, 表示已使用過(guò) t 年的卡車(chē), 再工作一年所需的

27、維修費(fèi), 它 隨 t 的增加而增加。 ct, t=1,2,.,k, 表示已使用過(guò) t 年的舊卡車(chē), 賣(mài)掉舊車(chē), 買(mǎi)進(jìn)新車(chē), 所 需的凈費(fèi)用, 它隨 t 的增加而增加。 設(shè)某卡車(chē)已使用過(guò) t 年, 如果繼續(xù)使用, 則第 t+1 年回收額為 Rt-Ut, 如果賣(mài)掉舊車(chē),買(mǎi)進(jìn)新車(chē), 則 第 t+1 年回收額為 R0-U0-Ct 46該運(yùn)輸戶(hù)從某年初購(gòu)車(chē)日起,計(jì)劃工作 N (N=20) 年, N 年后不論車(chē)的狀態(tài)如 何,不再工作. 為使這 N 年的總回收額最大, 應(yīng)在哪些年更新舊車(chē)? 假定在這 N 年內(nèi), 運(yùn)輸戶(hù)每年只用一輛車(chē), 而且以上各種費(fèi)用均不改變。 輸入: 用文件輸入已知數(shù)據(jù), 格式為: 第

28、1 行: N (運(yùn)輸戶(hù)工作年限) 第 2 行: k (卡車(chē)最大使用年限, k20 ) 第 3 行: R0 R1 . Rk 第 4 行: U0 U1 . Uk 第 5 行: C0 C1 . Ck 輸出: 用文本文件按以下格式輸出結(jié)果: 第 1 行: W ( N 年總回收額 ) 第 2-N+1 行: 每行輸出 3 個(gè)數(shù)據(jù): 年序號(hào) 是否更新 當(dāng)年回收額47例: 設(shè)給定以下數(shù)據(jù): N=4, k=5, i: 0 1 2 3 4 5 Ri: 8 7 6 5 4 2 Ui: 0.5 1 2 3 4 5 Ci: 0 2 3 5 8 10 則正確的輸出應(yīng)該是 24.5 1 0 7.5 2 1 5.5 3 1

29、5.5 4 0 6.0 48示例輸入文件內(nèi)容：4 58 7 6 5 4 20.5 1 2 3 4 50 2 3 5 8 10 卡車(chē)更新問(wèn)題有很多解法：動(dòng)態(tài)規(guī)劃算法（見(jiàn)程序設(shè)計(jì)培訓(xùn)講義9），下面是枚舉法的解題過(guò)程：49方法：枚舉算法（判斷所有可能的解）運(yùn)輸戶(hù)每年都有2種選擇：換新車(chē)與不換。設(shè)換車(chē)用1表示，不換車(chē)用0表示；則所有可能的解空間為：從100000 到 111 111，每個(gè)可能的解有n位。計(jì)算出每個(gè)可能的解的價(jià)值，即可得出最大值。下面程序中的數(shù)組bN用來(lái)循環(huán)所有的解，aN用來(lái)表示已求出的最大值的解空間(換新車(chē)與不換)，gN表示已求出的最大值的解空對(duì)應(yīng)的價(jià)值,m表示已求出的最大值。說(shuō)明：第

30、1年一定是用新車(chē)。50#include #define N 20float rN,uN,cN,dN,eN,fNN,m=0,gN;int aN,bN=0;int k,n;void output( )int i;printf(nn%fn,m);for (i=1; i=n; i+) printf(%dt%dt%8.1fn,i,ai-1,gi-1); int pow(int k) int i,s=1;for (i=1; i=k; i+) s=s*2;return s; 51void input()int i;char str80;FILE *fp;printf(input :);scanf(%s,st

31、r); fp=fopen(str,r);fscanf(fp,%d,&n);fscanf(fp,%d,&k);for (i=0; i=k; i+)fscanf(fp,%f,&ri);for (i=0; i=k; i+)fscanf(fp,%f,&ui);for (i=0; i=k; i+)fscanf(fp,%f,&ci);fclose(fp);52void disp ( ) int i;printf(%dn,n);printf(%dn,k);for (i=0; i=k; i+) printf(%8.1f,ri);printf(n);for (i=0; i=k; i+) printf(%8.1f

32、,ui);printf(n);for (i=0; i=k; i+) printf(%8.1f,ci);printf(n);53void max( )int i,t=1;float m2;m2=d0; g0=d0;for (i=1; im )m=m2;for (i=0; in; i+ )ai=bi;54void main()int i,j,t;input();disp();for (i=0; i=k; i+)di=ri-ui;ei=d0-ci; for (i=0; i=k; i+) fn+1i=0;for (i=1; i=n+1; i+) fik+1=0;for (i=0; ipow(n-1);

33、 i+)t=i;for (j=1; jn-1; j+) bj=t%2; t=t/2; max(); output(); 55例5：組合問(wèn)題 找出從自然數(shù)1、2、n中任取r個(gè)數(shù)的所有組合。例如n=5，r=3的所有組合為：（1）5、4、3（2）5、4、2（3）5、4、1 （4）5、3、2（5）5、3、1（6）5、2、1 （7）4、3、2（8）4、3、1（9）4、2、1 （10）3、2、1 枚舉法程序見(jiàn)（程序設(shè)計(jì)講義4）56例6：棋盤(pán)問(wèn)題。在44的棋盤(pán)上放置8個(gè)棋,要求每一行,每一列上只能放置2個(gè)。找出所有可能的解并輸出解的個(gè)數(shù)。 (回溯算法見(jiàn)程序設(shè)計(jì)培訓(xùn)講義8)枚舉思想1：用二維數(shù)組a44存放所有

34、可能的解（1表示放，0表示不放）。依次對(duì)數(shù)組每一行循環(huán)，如果第i行滿(mǎn)足條件（2個(gè)1），再進(jìn)入下一行。如果所有行（共4行）都滿(mǎn)足條件，說(shuō)明已生成二維數(shù)組a44 ；再判斷二維數(shù)組a44 所有列（共4列）是否滿(mǎn)足條件，如果滿(mǎn)足，則輸出。57#include int a44=0,sum=0;int f(int x,int i) /將x轉(zhuǎn)換成二進(jìn)制存入數(shù)組的第i行int j,s=0;for (j=3; j=0; j-)aij=x%2; s=s+x%2; x=x/2; if (s=2) return 1; else return 0; void output( ) /輸出解for (int i=0; i4

35、; i+)printf(n);for (int j=0; j4; j+)printf(%2d,aij);printf(n);58void pd( ) /判斷二維數(shù)組a44的每一列是否滿(mǎn)足條件int i,j,s;for (j=0;j4; j+)s=0;for (i=0; i4; i+) s=s+aij;if ( s!=2) break;if (s=2) sum+;output( ); 59void main( )int m,n,k,t;for ( m=0; m16; m+) /第0行if ( f(m,0) )for (n=0; n16; n+) /第1行if ( f(n,1) )for ( k=0; k16; k+) /第2行if ( f(k,2) )for ( t=0; t16;