C語言窮舉法經(jīng)典例題-文檔資料

1、第第3 3章章 程序控制結(jié)構(gòu)程序控制結(jié)構(gòu)枚舉法（窮舉法）枚舉法（窮舉法） “笨人之法笨人之法”： 把所有可能的情況一一測試，篩選出符合把所有可能的情況一一測試，篩選出符合條件的各種結(jié)果進(jìn)行輸出。條件的各種結(jié)果進(jìn)行輸出。分析：分析： 這是個不定方程這是個不定方程三元一次方程組問題三元一次方程組問題 （三個變量，兩個方程）（三個變量，兩個方程） 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章章 程序控

4、制結(jié)構(gòu)程序控制結(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)第第

5、3 3章章 程序控制結(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)信來了之后，校長問這四位是誰做的好事。之后

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

7、程序控制結(jié)構(gòu)顯然，就是顯然，就是CC做了好事（做了好事（四個關(guān)系表達(dá)式值之和為四個關(guān)系表達(dá)式值之和為3 3）這時，我們可以理出頭緒，要用枚舉法，一個人一個人地去這時，我們可以理出頭緒，要用枚舉法，一個人一個人地去試，四句話中有三句為真，該人即所求。試，四句話中有三句為真，該人即所求。第第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 =

8、 D);sd=(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ù)，最末一個士兵報(bào)的數(shù)為報(bào)數(shù)，最末一個士兵報(bào)的數(shù)為1；按從；按從1至至6報(bào)數(shù)，最末一個士兵報(bào)的數(shù)為報(bào)數(shù)，最末一個士兵報(bào)的數(shù)為5；按從；按從1至至7報(bào)數(shù)，報(bào)數(shù)，最末一個士兵報(bào)的數(shù)為最末一個士兵報(bào)的數(shù)為4；

9、最后再按從；最后再按從1至至11報(bào)數(shù)，最報(bào)數(shù)，最末一個士兵報(bào)的數(shù)為末一個士兵報(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窮舉法對窮舉法對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án)永遠(yuǎn)不會退出的循環(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;fo

11、r (x=1; ;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)兵:方