c語言枚舉法(窮舉法)課件

枚舉法（窮舉法）

“笨人之法”：

把所有可能的情況一一測試，篩選出符合條件的各種結(jié)果進(jìn)行輸出。分析：這是個不定方程——三元一次方程組問題

（三個變量，兩個方程）

x＋y＋z=100

5x＋3y＋z/3=100設(shè)公雞為x只，母雞為y只，小雞為z只。百元買百雞問題分析x＋y＋z=1005x＋3y＋z/3=100三重循環(huán)voidmain(){intx,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=%d\n",x,y,z);}}結(jié)果：x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84【討論】為什么多了幾組解?

?優(yōu)化voidmain(){intx,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=%d\n",x,y,z);}}【討論】

令z=100-x-y只進(jìn)行101×101=10201次運(yùn)算（前者的1%）

取x<=20,y<=33只進(jìn)行21×34=714次運(yùn)算（第1種運(yùn)算的6.9e-4）

繼續(xù)優(yōu)化voidmain(){intx,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=%d\n",x,y,z);}}

取x<=14,y<=25只進(jìn)行15×26=390次運(yùn)算利用窮舉法求解趣味智力題(韓信點(diǎn)兵)韓信有一隊兵，他想知道有多少人，便讓士兵排隊報數(shù)。按從1至5報數(shù)，最末一個士兵報的數(shù)為1；按從1至6報數(shù)，最末一個士兵報的數(shù)為5；按從1至7報數(shù)，最末一個士兵報的數(shù)為4；最后再按從1至11報數(shù)，最末一個士兵報的數(shù)為10。你知道韓信至少有多少兵嗎？設(shè)兵數(shù)為x，則x應(yīng)滿足：x%5==1&&x%6==5&&x%7==4&&x%11==10窮舉法對x從1開始試驗#include<stdio.h>voidmain(){

intx;

for(x=1;;x++) {

if(x%5==1&&x%6==5&&x%7==4&&x%11==10) { printf("x=%d\n",x); } } }/*死循環(huán)——永遠(yuǎn)不會退出的循環(huán)*/窮舉法求解韓信點(diǎn)兵窮舉法求解韓信點(diǎn)兵：方案2-break#include<stdio.h>voidmain(){

intx;

for(x=1;;x++) {

if(x%5==1&&x%6==5&&x%7==4&&x%11==10) { printf("x=%d\n",x);

break;

} } }課堂討論：誰做的好事？有四位同學(xué)中的一位做了好事，不留名，表揚(yáng)信來了之后，校長問這四位是誰做的好事。A說：不是我。B說：是C。C說：是D。D說：C胡說。已知三個人說的是真話，一個人說的是假話?，F(xiàn)在要根據(jù)這些信息，找出做了好事的人。編程思路：如何找到該人，一定是“先假設(shè)該人是做好事者，然后到每句話中去測試看有幾句是真話”?！坝腥涫钦嬖捑痛_定是該人，否則換下一人再試”。比如，先假定是A同學(xué)，讓thisman='A';

代入到四句話中A說：thisman!=‘A’; ‘A’!=‘A’ 假，值為0。B說：thisman==‘C’; ‘A’==‘C’ 假，值為0。C說：thisman==‘D’; ‘A’==‘D’ 假，值為0。D說：thisman!=‘D’; ‘A’!=‘D’ 真，值為1。顯然，不是'A'做的好事（四個關(guān)系表達(dá)式值的和為1）再試B同學(xué)，讓thisman=‘B’; 代入到四句話中A說：thisman!=‘A’; ‘B’!=‘A’ 真，值為1。B說：thisman==‘C’; ‘B’==‘C’ 假，值為0。C說：thisman==‘D’; ‘B’==‘D’ 假，值為0。D說：thisman!=‘D’; ‘B’!=‘D’ 真，值為1。顯然，不是'B'所為（四個關(guān)系表達(dá)式值的和為2）再試C同學(xué)，讓thisman=‘C’;

代入到四句話中A說：thisman!=‘A’; ‘C’!=‘A’ 真，值為1。B說：thisman==‘C’; ‘C’==‘C’ 真，值為1。C說：thisman==‘D’; ‘C’==‘D’ 假，值為0。D說：thisman!=‘D’;‘C’!=‘D’ 真，值為1。顯然，就是‘C’做了好事（四個關(guān)系表達(dá)式值之和為3）這時，我們可以理出頭緒，要用枚舉法，一個人一個人地去試，四句話中有三句為真，該人即所求。#include<stdio.h>voidmain(){ charthisman;

intsa,sb,sc,sd,cond;

for(thisman='A';thisman<='D';thisman++) { sa=(thisman!='A'); sb=(t