用窮舉法設(shè)計(jì)算法

1、n問題問題1： 有一把鎖和一串鑰匙（共有有一把鎖和一串鑰匙（共有10把鑰匙），把鑰匙），怎樣找出所有開這把鎖的鑰匙？怎樣找出所有開這把鎖的鑰匙？n窮舉算法的概念：窮舉算法的概念： 窮舉算法窮舉算法就是按問題本身的性質(zhì)，通過就是按問題本身的性質(zhì)，通過多多重循環(huán)重循環(huán)一一列舉出該問題所有可能的解（一一列舉出該問題所有可能的解（不能不能遺漏，也不能重復(fù)遺漏，也不能重復(fù)），并在逐一列舉的過程中，），并在逐一列舉的過程中，檢驗(yàn)每個(gè)可能的解是否是問題的真正解檢驗(yàn)每個(gè)可能的解是否是問題的真正解，若是，若是，我們采用這個(gè)解，否則拋棄它。我們采用這個(gè)解，否則拋棄它。n 窮舉算法的要點(diǎn)：窮舉算法的要點(diǎn)： 列舉所有

2、可能的解（不能遺漏，也不能重列舉所有可能的解（不能遺漏，也不能重 復(fù)），檢驗(yàn)每個(gè)可能的解。復(fù)），檢驗(yàn)每個(gè)可能的解。 問題問題2：從：從110中找出所有中找出所有是是3倍數(shù)倍數(shù)的數(shù)。的數(shù)。用用流程圖描述流程圖描述解決此數(shù)學(xué)問題的算法。解決此數(shù)學(xué)問題的算法。輸出輸出i i開始開始i1i1i10i10i i +1i i +1結(jié)束結(jié)束NYi i是是3 3的倍數(shù)的倍數(shù)YN#includeusing namespace std;int main()int i=1; while(i=10) if (i%3=0) printf(“%dn”,i); i=i+1; 問題問題3：從：從1100中找出所有中找出所有能

3、被能被7或或9整除整除的數(shù)。用的數(shù)。用流程圖描述流程圖描述解決此數(shù)學(xué)問題的算法。解決此數(shù)學(xué)問題的算法。輸出輸出i i開始開始i1i1i100i100i i +1i i +1結(jié)束結(jié)束NYi i能被能被7 7或或9 9整除整除YN#includeusing namespace std;int main()int i; for(i=1;i=100;i=i+1) if (i%7=0|i%9=0) printf(“%dn”,i); 問題問題4：打印輸出由：打印輸出由1、28、9這九個(gè)數(shù)字組成的所有可能的二位這九個(gè)數(shù)字組成的所有可能的二位數(shù)數(shù)n。用流程圖描述。用流程圖描述。分析：分析：個(gè)位數(shù)個(gè)位數(shù)上的數(shù)字

4、可以是那幾種上的數(shù)字可以是那幾種數(shù)字？用數(shù)字？用變量變量i來表示。來表示。十位數(shù)十位數(shù)上的數(shù)字可以是那幾種上的數(shù)字可以是那幾種數(shù)字？數(shù)字？用變量用變量j來表示。來表示。找出二位數(shù)找出二位數(shù)n與與i、j之間的關(guān)之間的關(guān)系。提示：系。提示：548=5100+410+8輸出輸出n n開始開始j j11j j99i i i i +1 +1結(jié)束結(jié)束NNi i11Yi i99nj j* *10+10+i iYj j j j +1 +1執(zhí)行過程：執(zhí)行過程：j=1in3456789 102111 12 13 14 1516 17 18 19j=2#includeusing namespace std;int

5、main() int j,i,n; j=1; While(j=9) i=1; While(i=9) n=j*10+i; printf(“%d”,n); i=i+1; j=j+1; 問題問題4：打印輸出由：打印輸出由1、28、9這九個(gè)數(shù)這九個(gè)數(shù)字組成的所有可能的二位數(shù)字組成的所有可能的二位數(shù)n。#includeusing namespace std;int main() int i,j; for (i=1;i=9;i+) for (j=1;j=9;j+) printf(%dn,i*10+j); return 0; 標(biāo)準(zhǔn)輸入輸出速度比較快。標(biāo)準(zhǔn)輸入輸出速度比較快。流輸入輸出在數(shù)據(jù)比較多，比流輸入輸

6、出在數(shù)據(jù)比較多，比如如1000000個(gè)數(shù)據(jù)的時(shí)候會(huì)很個(gè)數(shù)據(jù)的時(shí)候會(huì)很慢。慢。ios:sync_with_stdio(false) 采用窮舉算法解題的基本思想：采用窮舉算法解題的基本思想：（1） 明確問題要求，確定枚舉對(duì)象，用合適類型明確問題要求，確定枚舉對(duì)象，用合適類型的變量表示枚舉對(duì)象。的變量表示枚舉對(duì)象。（2） 明確枚舉對(duì)象的取值范圍。明確枚舉對(duì)象的取值范圍。（3） 根據(jù)題目要求，寫出有關(guān)的條件表達(dá)式。這根據(jù)題目要求，寫出有關(guān)的條件表達(dá)式。這里條件表達(dá)式可以是數(shù)學(xué)表達(dá)式、關(guān)系表達(dá)式或里條件表達(dá)式可以是數(shù)學(xué)表達(dá)式、關(guān)系表達(dá)式或邏輯表達(dá)式；邏輯表達(dá)式；（4） 使用循環(huán)語句枚舉出可能的解，在循環(huán)

7、體內(nèi)使用循環(huán)語句枚舉出可能的解，在循環(huán)體內(nèi)驗(yàn)證各種條表達(dá)式是否滿足；驗(yàn)證各種條表達(dá)式是否滿足；（5） 根據(jù)問題背景，優(yōu)化程序，以便縮小搜索范根據(jù)問題背景，優(yōu)化程序，以便縮小搜索范圍，減少程序運(yùn)行時(shí)間。圍，減少程序運(yùn)行時(shí)間。【例5】：（百錢買百雞問題）大約在公元5世紀(jì)，數(shù)學(xué)家張邱建在他的算經(jīng)中提出了一個(gè)聞名于后世的百錢百雞問題：雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一，百錢買百雞，翁、母、雛各幾何？1.算法分析與設(shè)計(jì)(1) 以三種雞的個(gè)數(shù)為枚舉對(duì)象，分別設(shè)為x,y,z。根據(jù)題意，可以列出下面的不定方程(2)確定枚舉變量的取值范圍。顯然，x，y，z的取值范圍為 0 x,y,z100;#inc

8、ludeusing namespace std;int 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=75x=3,y=20,z=77x=4,y=18,z=78x=7,y=13,z=80 x=8,y=11,z=81x=11,y=6,z=83x=12,y=4,z=84有錯(cuò)誤#includeusing namespace std;int main()

9、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 & 15*x+9*y+z=300) printf(x=%d,y=%d,z=%dn,x,y,z);修改錯(cuò)誤x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84#includeint main() int x,y,z; for(x=0;x=20;x+) for(y=0;y=33;y+) for(z=0;z=100;z+) if(x+y+z=100 & 15*x+9*y+z=30

10、0) printf(x=%d,y=%d,z=%dn,x,y,z);第1次優(yōu)化x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84Press any key to continue只要求出x，y后，z可以由方程(4)直接計(jì)算出來。在方程（3）中，假設(shè)y=0,則x=14,假設(shè)x=0,則y=25。即x,y的枚舉范圍是 0 x14,0y25.for(x=0;x=14;x+) for(y=0;y=25;y+) if(7*x+4*y=100) z=100-x-y; output(x,y,z); 第2次優(yōu)化#includeusing namespace s

11、td;int 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(x=%d,y=%d,z=%dn,x,y,z); x=0,y=25,z=75x=4,y=18,z=78x=8,y=11,z=81x=12,y=4,z=84Press any key to continue邏輯推理問題n邏輯推理問題【例6】：（誰做的好事）已知有有四位同學(xué)中的一位做了好事，不留名，表揚(yáng)信來了之后，校長(zhǎng)問這四位是誰做的好事。A說：不是我。B說：是C。C說：是D。D說：他胡說。已知三個(gè)人說的是真話，一個(gè)

12、人說的是假話?，F(xiàn)在要根據(jù)這些信息，找出做了好事的人。1.算法分析將相關(guān)的陳述寫成關(guān)系表達(dá)式和邏輯表達(dá)式我們把四個(gè)人說的四句話寫成關(guān)系表達(dá)式。定義變量thisman表示做好事的人（將其定義為字符型）。四個(gè)人說的話關(guān)系表達(dá)式A說：不是我。thisman!=AB說：是C。thisman=CC說：是D。thisman=DD說：他胡說。thisman!=D關(guān)系表達(dá)式的計(jì)算結(jié)果只有0（假）和1（真）兩種結(jié)果?，F(xiàn)在“已知三個(gè)人說的是真話，一個(gè)人說假話”，也就是表中的4個(gè)關(guān)系表達(dá)式中有3個(gè)是真的，1個(gè)是假的。 因此4個(gè)關(guān)系表達(dá)式的值的和應(yīng)該等于3。定義變量cond表示四個(gè)關(guān)系表達(dá)式的和 cond= thism

13、an!=A+ thisman=C+ thisman=D+ thisman!=D 那么，cond=3窮舉試探。我們現(xiàn)在并不知道是誰做得好事，但我們知道做好事的人是A,B,C,D四個(gè)人中的某一個(gè)。因此，我們可以一個(gè)一個(gè)地試探。先假設(shè)是A做的好事，即thisman=A，然后看cond=3條件是否成立，然后再假設(shè)是B做的好事，即thisman=B,再測(cè)試條件cond=3 是否成立，如此繼續(xù)下去，將所有可能的情況（本例自有4種情況）都測(cè)試一遍，在實(shí)際編程過程中，都是使用循環(huán)來一個(gè)一個(gè)的測(cè)試 for(thisman=A;thisman=D;thisman+) cond=(thisman!=A)+(this

14、man=C) +(thisman=D)+(thisman!=D); if(cond=3)printf(做好事的人是：%Cn,thisman); 2. 核心代碼#includeusing namespace std;int main() char thisman;int cond;for(thisman=A; thisman=D;thisman+) cond=(thisman!=A)+(thisman=C) +(thisman=D)+(thisman!=D);if(cond=3)printf(做好事的人是：%Cn,thisman); 【例7】: (四大湖問題)上地理課時(shí)，四個(gè)學(xué)生回答我國(guó)四個(gè)淡水

15、湖大小時(shí)說： A學(xué)生：洞庭湖最大，洪澤湖最小，鄱陽湖第3 B學(xué)生：洪澤湖最大，洞庭湖最小，鄱陽湖第2，太湖第3 C學(xué)生：洪澤湖最小，洞庭湖第3 D學(xué)生：鄱陽湖最大，太湖最小，洪澤湖第2，洞庭第3 對(duì)于湖的大小，每個(gè)學(xué)生僅答對(duì)一個(gè)，請(qǐng)編程判斷四個(gè)湖的大小1.分析與算法設(shè)計(jì) (1)定義變量： a洞庭湖，a可能的取值1,2,3,4 b洪澤湖，b可能的取值1,2,3,4 c鄱陽湖，c可能的取值1,2,3,4 d太湖，d可能的取值1,2,3,4a,b,c,d四個(gè)變量的取值互不相同，1表示最大，四表最小(2) 用變量表示條件 A學(xué)生的敘述可表示為：a=1, b=4,c=3 這是三個(gè)關(guān)系表達(dá)式，由于每個(gè)學(xué)生

16、的敘述只有一個(gè)正確，所以這三個(gè)關(guān)系表達(dá)式的值的和應(yīng)等于1。 A學(xué)生的敘述可表示成： ( (a=1)+(b=4)+(c=3）)=1 同理，B學(xué)生的敘述表示成： (b=1)+(a=4)+(c=2)+(d=3)=1 C學(xué)生的敘述可表示成： (b=4)+(a=3) =1 D學(xué)生的敘述可表示成： (c=1)+(d=4)+(b=2)+(a=3)=1for(a=1;a=4;a+) for(b=1;b=4;b+) for(c=1;c=4;c+) for(d=1;d=4;d+) ca=(a=1）+（b=4）+(c=3）)=1; cb=(b=1)+(a=4)+(c=2)+(d=3)=1; cc=(b=4)+(a=

17、3) )=1; cd=(c=1)+(d=4)+(b=2)+(a=3)=1; if(ca & cb & cc & cd) printf(TongTing=%dn,a); printf(Hongzhe=%dn,b);printf(Poyang=%dn,c); printf(Taihu=%dn,d); /end for(3) 窮舉: 窮舉a,b,c,d四個(gè)變量的所有可能取值,進(jìn)行測(cè)試，滿足前述四個(gè)條件的取值就是我們所要的結(jié)果【例8】（白帽子和紅帽子問題）廳內(nèi)有5個(gè)人，他們均戴著帽子白帽子和紅帽子。已知戴白帽子的說真話，戴紅帽子的說假話，請(qǐng)從他們各自提供的線索辨別誰戴白帽子，誰

18、戴紅帽子。甲：我看見一個(gè)戴白帽子的乙：我沒有看見戴紅帽子的丙：我看見一個(gè)戴白帽子的，但不是甲?。何覜]有看見戴白帽子的戊：我的帽子和丙一樣 定義變量 用5個(gè)整型變量a,b,c,d,e分別表示甲、乙、丙、丁、戊，1表示戴白帽子，0表示戴紅帽子。 寫出五個(gè)人所說的每句話的邏輯表達(dá)式甲：(b+c+d+e=1)乙：(a+c+d+e=4)丙：(b+d+e=1)?。?a+b+c+e=0)戊：(e=c)這里只是簡(jiǎn)單地將五個(gè)人說的話寫成了表達(dá)式，但這還不夠，由于這五個(gè)人本身有些說真話，有些說假話，因此如何判斷上述五個(gè)表達(dá)式的真假呢？ 思考：每個(gè)人說話的真假與他所戴的帽子有關(guān)，如果他戴的是白帽子，則他說真話；如果

19、他戴的是紅帽子，則他所說的是假話，這樣將每個(gè)人帽子顏色與他說的話直接聯(lián)系起來，因此上述條件可表示成： 甲：(b+c+d+e=1)=a乙：(a+c+d+e=4)=b丙：(b+d+e=1)=c?。?a+b+c+e=0)=d戊：(e=c)=evoid main()int a,b,c,d,e,c1,c2,c3,c4,c5;for(a=0;a=1;a+) for(b=0;b=1;b+)for(c=0;c=1;c+) for(d=0;d=1;d+) for(e=0;e=1;e+)c1=(b+c+d+e=1)=a;c2=(a+c+d+e=4)=b;c3=(b+d+e=1)=c;c4=(a+b+c+e=0)=

20、d;c5=(e=c)=e;if(c1 & c2 & c3 & c4 & c5) printf(a=%d,b=%d,c=%d,d=%d,e=%dn, a,b,c,d,e) ; 窮舉：對(duì)變量a,b,c,d,e的所有可能取值情況進(jìn)行枚舉，這要用一個(gè)5重循環(huán)實(shí)現(xiàn)。例例9 9：輸入繩子的長(zhǎng)度：輸入繩子的長(zhǎng)度n n，將該繩子分成三段，每段，將該繩子分成三段，每段的長(zhǎng)度為正整數(shù)，輸出由該三段繩子組成的三角的長(zhǎng)度為正整數(shù)，輸出由該三段繩子組成的三角形個(gè)數(shù)。形個(gè)數(shù)。 s=0;s=0;for for （a=1;a=n-2;a+a=1;a=n-2;a+） for for （b=a;b

21、=n-2;b+b=a;b=n-2;b+） for for （c=b;c=n-2;c+c=b;cc) & (b+ca) & (c+ab) & if (a+bc) & (b+ca) & (c+ab) & (a+b+c=n) )(a+b+c=n) ) s+; s+;窮舉法的基本概念 窮舉算法模式 1、問題解的可能搜索的范圍：?jiǎn)栴}解的可能搜索的范圍： 用循環(huán)或循環(huán)嵌套結(jié)構(gòu)實(shí)現(xiàn)用循環(huán)或循環(huán)嵌套結(jié)構(gòu)實(shí)現(xiàn) 2、寫出符合問題解的條件。寫出符合問題解的條件。 3、能使程序優(yōu)化的語句，以便縮小搜索范能使程序優(yōu)化的語句，以便縮小搜索范 圍，減少程序運(yùn)行時(shí)間。圍，減少程

22、序運(yùn)行時(shí)間。 窮舉法應(yīng)用 窮舉法應(yīng)用很多，比如一些密碼破譯軟件通窮舉法應(yīng)用很多，比如一些密碼破譯軟件通常就是用的窮舉算法。如在常就是用的窮舉算法。如在QQQQ上，上，OicqPassOverOicqPassOver這個(gè)工具窮舉你的口令，它根這個(gè)工具窮舉你的口令，它根據(jù)機(jī)器性能最高可以每秒測(cè)試據(jù)機(jī)器性能最高可以每秒測(cè)試2000020000個(gè)口令，個(gè)口令，如果口令簡(jiǎn)單，一分鐘內(nèi)，密碼就會(huì)遭到破如果口令簡(jiǎn)單，一分鐘內(nèi)，密碼就會(huì)遭到破譯。下面我們來以譯。下面我們來以sznoisznoi上的例子說明窮舉上的例子說明窮舉法的基本應(yīng)用。法的基本應(yīng)用。 d052: 小球顏色方案內(nèi)容：內(nèi)容：一個(gè)看不見的袋子中裝

23、有紅、橙、黃、綠、藍(lán)五種顏色的小球若干，每次隨意摸出三個(gè)小球，輸出三個(gè)小球顏色都不一樣的所有可能的方案總數(shù)。（我承認(rèn)害了不少人，大家認(rèn)為：紅、橙、黃 和 橙、紅、黃不一樣吧，這樣就是XX種，謝謝）d052: 小球顏色方案#includeusing namespace std;int main() int a,b,c,n=0; for (a=1;a=5;a+) for (b=1;b=5;b+) for (c=1;c=5;c+) if (a!=b&b!=c&a!=c) n+; coutnendl; return 0; d058: 勾股數(shù) 內(nèi)容：內(nèi)容：20以內(nèi)勾股數(shù)（假設(shè)a=b=c)

24、a2+b2=c2 若有多組，按a從小到大順序輸出 .輸入說明：輸入說明：無輸出說明：輸出說明：一行一組三個(gè)數(shù)，用空格隔開d058: 勾股數(shù) #include using namespace std; int main() int a,b,c; for (a=1;a=20;a+) for (b=a;b=20;b+) for (c=b;c=20;c+) if (a*a+b*b=c*c) couta b cendl; return 0; d071: 倒立勾股數(shù) 關(guān)鍵字： 內(nèi)容：內(nèi)容：1/x2+1/y2=1/z2 其中正整數(shù)xyz成為一組倒立的勾股數(shù)！注意，是正整數(shù)哦！你的任務(wù)是輸出60以內(nèi)的倒立勾股

25、數(shù)，按x的的增序輸出（每行一個(gè)）。 d071: 倒立勾股數(shù) #includeusing namespace std;int main()int x,y,z;for(x=1;x=60;x+) for(y=1;y=60;y+) for(z=1;z=60;z+)if(x*x*y*y=z*z*(x*x+y*y)&x=y)printf(%d %d %dn,x,y,z);return 0;f003: AB類數(shù) (NOIP1995)內(nèi)容：內(nèi)容：若將一個(gè)正整數(shù)化為二進(jìn)制數(shù)，在此二進(jìn)制數(shù)中，我們將數(shù)字1的個(gè)數(shù)多于數(shù)字0的個(gè)數(shù)的這類二進(jìn)制數(shù)稱為A類數(shù)，否則就稱其為B類數(shù)。例如：（13）10=（1101）2其中1的個(gè)數(shù)為3，0的個(gè)數(shù)為1，則稱此數(shù)為A類數(shù)；（10）10=（1010）2其中1的個(gè)數(shù)為2，0的個(gè)數(shù)也為2，稱此數(shù)為B類數(shù)；（24）10=（11000）2其中1的個(gè)數(shù)為2，0的個(gè)數(shù)為3，則稱此數(shù)為B類數(shù)；程序要求：