C語言窮舉法經(jīng)典例題課件

枚舉法（窮舉法）

“笨人之法”：

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

（三個(gè)變量，兩個(gè)方程）

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)算課堂討論：誰做的好事？有四位同學(xué)中的一位做了好事，不留名，表揚(yáng)信來了之后，校長問這四位是誰做的好事。A說：不是我。B說：是C。C說：是D。D說：C胡說。已知三個(gè)人說的是真話，一個(gè)人說的是假話?，F(xiàn)在要根據(jù)這些信息，找出做了好事的人。再試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'所為（四個(gè)關(guān)系表達(dá)式值的和為2）#include<stdio.h>voidmain(){ charthisman;

intsa,sb,sc,sd,cond;

for(thisman='A';thisman<='D';thisman++) { sa=(thisman!='A'); sb=(thisman=='C'); sc=(thisman=='D'); sd=(thisman!='D');

cond=sa+sb+sc+sd;

if

(cond==3) printf("做好事的人是：%c\n",thisman); }}#include<stdio.h>voidmain(){

intx;

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

if(x%5==1&&x%6==5&&x%7==4&&x%11==10) { printf("x=%d\n",x); } } }/*屬于“瞎貓碰死耗子”的做法*/窮舉法求解韓信點(diǎn)兵#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ì)退出的循環(huán)*/窮舉法求解韓信點(diǎn)兵窮舉法求解韓信點(diǎn)兵：方案1-goto#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);

goto

END;

} }

END:;

}窮舉法求解韓信點(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;

} } }窮舉法求解韓信點(diǎn)兵:方案3-標(biāo)志變量#include<stdio.h>voidmain(){

intx;

int

find=0;/*設(shè)置找到標(biāo)志為假*