C語(yǔ)言窮舉法經(jīng)典例題

枚舉法（窮舉法）

“笨人之法”：

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

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

x＋y＋z=100

5x＋3y＋z/3=100

設(shè)公雞為x只，母雞為y只，小雞為z只。百元買百雞問(wèn)題分析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【討論】為什么多了幾組解?

?百元買百雞問(wèn)題分析voidmain(){

intx,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=%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【討論】

此為“最笨”之法——要進(jìn)行101×101×101=1030301次（100多萬(wàn)次）運(yùn)算。優(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)算課堂討論：誰(shuí)做的好事？有四位同學(xué)中的一位做了好事，不留名，表?yè)P(yáng)信來(lái)了之后，校長(zhǎng)問(wèn)這四位是誰(shuí)做的好事。

A說(shuō)：不是我。

B說(shuō)：是C。

C說(shuō)：是D。

D說(shuō)：C胡說(shuō)。已知三個(gè)人說(shuō)的是真話，一個(gè)人說(shuō)的是假話?，F(xiàn)在要根據(jù)這些信息，找出做了好事的人。編程思路：

如何找到該人，一定是“先假設(shè)該人是做好事者，然后到每句話中去測(cè)試看有幾句是真話”?！坝腥涫钦嬖捑痛_定是該人，否則換下一人再試”。比如，先假定是A同學(xué)，讓thisman='A';

代入到四句話中

A說(shuō)：thisman!=‘A’; ‘A’!=‘A’ 假，值為0。

B說(shuō)：thisman==‘C’; ‘A’==‘C’ 假，值為0。

C說(shuō)：thisman==‘D’; ‘A’==‘D’ 假，值為0。

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

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

thisman;

int

sa,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); }}利用窮舉法求解趣味智力題(韓信點(diǎn)兵)韓信有一隊(duì)兵，他想知道有多少人，便讓士兵排隊(duì)報(bào)數(shù)。按從1至5報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為1；按從1至6報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為5；按從1至7報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為4；最后再按從1至11報(bào)數(shù)，最末一個(gè)士兵報(bào)的數(shù)為10。你知道韓信至少有多少兵嗎？設(shè)兵數(shù)為x，則x應(yīng)滿足：x%5==1&&x%6==5&&x%7==4&&x%11==10窮舉法對(duì)x從1開始試驗(yàn)#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>voi