窮舉法經(jīng)典例題

1、第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)枚舉法（窮舉法）枚舉法（窮舉法） “笨人之法笨人之法”： 把所有可能的情況一一測(cè)試，篩選出符合把所有可能的情況一一測(cè)試，篩選出符合條件的各種結(jié)果進(jìn)行輸出。條件的各種結(jié)果進(jìn)行輸出。分析：分析： 這是個(gè)不定方程這是個(gè)不定方程三元一次方程組問題三元一次方程組問題 （三個(gè)變量，兩個(gè)方程）（三個(gè)變量，兩個(gè)方程） xyz=100 5x3yz/3=100 設(shè)公雞為設(shè)公雞為x只，母雞為只，母雞為y只，小雞為只，小雞為z只。只。 第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)百元買百雞問題分析百元買百雞問題分析x xy yz=100z=1005x5x3y3yz/3=100z/3

2、=100三重循環(huán)第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)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 (x+y+z=100 & 5*x+3*y+z/3=100 ) printf(x=%d,y=%d,z=%dn,x,y,z); 結(jié)果：x=0,y=25,z=75 x=4,y=18,z=78 x=8,y=11,z=81 x=12,y=4,z=84【討論討論】為什么多了幾組解為什么多了幾組解? ? ? ?第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)百元買百雞問題分析百元買百雞問題

3、分析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 (z%3=0 &x+y+z=100 & 5*x+3*y+z/3=100 ) printf(x=%d,y=%d,z=%dn,x,y,z); 結(jié)果：x=0,y=25,z=75 x=4,y=18,z=78 x=8,y=11,z=81 x=12,y=4,z=84【討論討論】 此為此為“最笨最笨”之法之法要進(jìn)行要進(jìn)行101101101= 1030301次次（100多萬次）運(yùn)算。多萬次）運(yùn)算。第第3 3章章 程序控制結(jié)構(gòu)程

4、序控制結(jié)構(gòu)優(yōu)化優(yōu)化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(cocks=%d,hens=%d,chickens=%dn,x,y,z); 【討論討論】 令令z=100-x-y 只進(jìn)行只進(jìn)行101101= 10201 次運(yùn)算（前者的次運(yùn)算（前者的1%） 取取x=20,y=33 只進(jìn)行只進(jìn)行2134= 714 次運(yùn)算（第次運(yùn)算（第1種運(yùn)算的種運(yùn)算的6.9e-4） 第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)第第3 3章章

5、程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)繼續(xù)優(yōu)化繼續(xù)優(yōu)化void main() int x,y,z; for (x=0;x=14;x+) for (y=0;y=25;y+) if (7*x+4*y=100 ) z=100-x-y; printf(cocks=%d,hens=%d,chickens=%dn,x,y,z); 取取x=14,y=25 只進(jìn)行只進(jìn)行1526= 390 次運(yùn)算次運(yùn)算第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)課堂討論：誰做的好事？課堂討論：誰做的好事？ 有四位同學(xué)中的一位做了好事，不留名，表揚(yáng)信來了有四位同學(xué)中的一位做了好事，不留名，表揚(yáng)信來了之后，校長(zhǎng)問這四位是誰做的好事。之后，校長(zhǎng)問這四

6、位是誰做的好事。 A A說：不是我。說：不是我。 B B說：是說：是C C。 C C說：是說：是D D。 D D說：說：C C胡說。胡說。 已知三個(gè)人說的是真話，一個(gè)人說的是假話?，F(xiàn)在要根據(jù)已知三個(gè)人說的是真話，一個(gè)人說的是假話。現(xiàn)在要根據(jù)這些信息，找出做了好事的人。這些信息，找出做了好事的人。第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)顯然，不是顯然，不是AA做的好事（做的好事（四個(gè)關(guān)系表達(dá)式值的和為四個(gè)關(guān)系表達(dá)式值的和為1 1）第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)顯然，不是顯然，不是BB所為（所為（四個(gè)關(guān)系表達(dá)式值的和為四個(gè)關(guān)系表達(dá)式值的和為2 2）第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)

7、顯然，就是顯然，就是CC做了好事（做了好事（四個(gè)關(guān)系表達(dá)式值之和為四個(gè)關(guān)系表達(dá)式值之和為3 3）這時(shí)，我們可以理出頭緒，要用枚舉法，一個(gè)人一個(gè)人地去這時(shí)，我們可以理出頭緒，要用枚舉法，一個(gè)人一個(gè)人地去試，四句話中有三句為真，該人即所求。試，四句話中有三句為真，該人即所求。第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)#includevoid main( )char thisman;int sa,sb,sc,sd,cond;for (thisman=A; thisman=D; thisman+)sa=(thisman != A);sb=(thisman = C);sc=(thisman = D);sd

8、=(thisman != D);cond=sa+sb+sc+sd;if (cond=3) printf(做好事的人是：做好事的人是：%cn, thisman);第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)利用窮舉法求解趣味智力題利用窮舉法求解趣味智力題(韓信點(diǎn)兵韓信點(diǎn)兵)韓信有一隊(duì)兵，他想知道有多少人，便讓士兵排隊(duì)報(bào)韓信有一隊(duì)兵，他想知道有多少人，便讓士兵排隊(duì)報(bào)數(shù)。按從數(shù)。按從1至至5報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為1；按從；按從1至至6報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為5；按從；按從1至至7報(bào)數(shù)，報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為最末一個(gè)士兵報(bào)的數(shù)為4；最后再按從；

9、最后再按從1至至11報(bào)數(shù)，最報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為末一個(gè)士兵報(bào)的數(shù)為10。你知道韓信至少有多少兵嗎？。你知道韓信至少有多少兵嗎？設(shè)兵數(shù)為設(shè)兵數(shù)為x，則，則x應(yīng)滿足：應(yīng)滿足：x%5 = 1 & x%6 = 5 & x%7 = 4 & x%11 = 10窮舉法對(duì)窮舉法對(duì)x從從1開始試驗(yàn)開始試驗(yàn)第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)#include void main()int x;for (x=1; x 5000 ;x+)if (x%5=1 & x%6=5 & x%7=4 & x%11=10)printf( x = %dn, x); /*屬于屬

10、于“瞎貓碰死耗子瞎貓碰死耗子”的做法的做法*/窮舉法求解韓信點(diǎn)兵窮舉法求解韓信點(diǎn)兵第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)#include void main()int x;for (x=1; ;x+)if (x%5=1 & x%6=5 & x%7=4 & x%11=10)printf( x = %dn, x); /*死循環(huán)死循環(huán)永遠(yuǎn)不會(huì)退出的循環(huán)永遠(yuǎn)不會(huì)退出的循環(huán)*/窮舉法求解韓信點(diǎn)兵窮舉法求解韓信點(diǎn)兵第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)窮舉法求解韓信點(diǎn)兵：方案窮舉法求解韓信點(diǎn)兵：方案1-goto#include void main()int x;for (x=1

11、; ;x+) if (x%5=1 & x%6=5 & x%7=4 & x%11=10)printf( x = %dn, x); goto END; END: ;第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)窮舉法求解韓信點(diǎn)兵：方案窮舉法求解韓信點(diǎn)兵：方案2-break#include void main()int x;for (x=1; ;x+) if (x%5=1 & x%6=5 & x%7=4 & x%11=10)printf( x = %dn, x); break; 第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)窮舉法求解韓信點(diǎn)兵窮舉法求解韓信點(diǎn)兵:方案方案3-標(biāo)志變量標(biāo)志變量#include void main()int x; int find =