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

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

2、=100三重循環(huán)第第3 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 (x+y+z=100 & 5*x+3*y+z/3=100 ) printf(x=%d,y=%d,z=%dn,x,y,z); 結果：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章章 程序控制結構程序控制結構百元買百雞問題分析百元買百雞

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); 結果：x=0,y=25,z=75 x=4,y=18,z=78 x=8,y=11,z=81 x=12,y=4,z=84【討論】【討論】 此為此為“最笨最笨”之法之法要進行要進行101101101= 1030301次次（100多萬次）運算。多萬次）運算。第第3 3章章 程序控

4、制結構程序控制結構優(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 只進行只進行101101= 10201 次運算（前者的次運算（前者的1%） 取取x=20,y=33 只進行只進行2134= 714 次運算（第次運算（第1種運算的種運算的6.9e-4） 第第3 3章章 程序控制結構程序控制結構第第

5、3 3章章 程序控制結構程序控制結構繼續(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 只進行只進行1526= 390 次運算次運算第第3 3章章 程序控制結構程序控制結構課堂討論：誰做的好事？課堂討論：誰做的好事？ 有四位同學中的一位做了好事，不留名，表揚信來了有四位同學中的一位做了好事，不留名，表揚信來了之后，校長問這四位是誰做的好事。之后

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

7、程序控制結構顯然，就是顯然，就是CC做了好事（做了好事（四個關系表達式值之和為四個關系表達式值之和為3 3）這時，我們可以理出頭緒，要用枚舉法，一個人一個人地去這時，我們可以理出頭緒，要用枚舉法，一個人一個人地去試，四句話中有三句為真，該人即所求。試，四句話中有三句為真，該人即所求。第第3 3章章 程序控制結構程序控制結構#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章章 程序控制結構程序控制結構利用窮舉法求解趣味智力題利用窮舉法求解趣味智力題(韓信點兵韓信點兵)韓信有一隊兵，他想知道有多少人，便讓士兵排隊報韓信有一隊兵，他想知道有多少人，便讓士兵排隊報數(shù)。按從數(shù)。按從1至至5報數(shù)，最末一個士兵報的數(shù)為報數(shù)，最末一個士兵報的數(shù)為1；按從；按從1至至6報數(shù)，最末一個士兵報的數(shù)為報數(shù)，最末一個士兵報的數(shù)為5；按從；按從1至至7報數(shù)，報數(shù)，最末一個士兵報的數(shù)為最末一個士兵報的數(shù)為4；

9、最后再按從；最后再按從1至至11報數(shù)，最報數(shù)，最末一個士兵報的數(shù)為末一個士兵報的數(shù)為10。你知道韓信至少有多少兵嗎？。你知道韓信至少有多少兵嗎？設兵數(shù)為設兵數(shù)為x，則，則x應滿足：應滿足：x%5 = 1 & x%6 = 5 & x%7 = 4 & x%11 = 10窮舉法對窮舉法對x從從1開始試驗開始試驗第第3 3章章 程序控制結構程序控制結構#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、 /*屬于屬于“瞎貓碰死耗子瞎貓碰死耗子”的做法的做法*/窮舉法求解韓信點兵窮舉法求解韓信點兵第第3 3章章 程序控制結構程序控制結構#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)永遠不會退出的循環(huán)永遠不會退出的循環(huán)*/窮舉法求解韓信點兵窮舉法求解韓信點兵第第3 3章章 程序控制結構程序控制結構窮舉法求解韓信點兵：方案窮舉法求解韓信點兵：方案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章章 程序控制結構程序控制結構窮舉法求解韓信點兵：方案窮舉法求解韓信點兵：方案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章章 程序控制結構程序控制結構窮舉法求解韓信點兵窮舉法求解韓信點兵:方