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

2、可能的解（不能遺漏，也不能重列舉所有可能的解（不能遺漏，也不能重 復），檢驗每個可能的解。復），檢驗每個可能的解。 問題問題2：從：從110中找出所有中找出所有是是3倍數倍數的數。的數。用用流程圖描述流程圖描述解決此數學問題的算法。解決此數學問題的算法。輸出輸出i i開始開始i1i1i10i10i i +1i i +1結束結束NYi i是是3 3的倍數的倍數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整除整除的數。用的數。用流程圖描述流程圖描述解決此數學問題的算法。解決此數學問題的算法。輸出輸出i i開始開始i1i1i100i100i i +1i i +1結束結束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這九個數字組成的所有可能的二位這九個數字組成的所有可能的二位數數n。用流程圖描述。用流程圖描述。分析：分析：個位數個位數上的數字

4、可以是那幾種上的數字可以是那幾種數字？用數字？用變量變量i來表示。來表示。十位數十位數上的數字可以是那幾種上的數字可以是那幾種數字？數字？用變量用變量j來表示。來表示。找出二位數找出二位數n與與i、j之間的關之間的關系。提示：系。提示：548=5100+410+8輸出輸出n n開始開始j j11j j99i i i i +1 +1結束結束NNi i11Yi i99nj j* *10+10+i iYj j j j +1 +1執行過程：執行過程：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這九個數這九個數字組成的所有可能的二位數字組成的所有可能的二位數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; 標準輸入輸出速度比較快。標準輸入輸出速度比較快。流輸入輸出在數據比較多，比流輸入輸

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

7、體內使用循環語句枚舉出可能的解，在循環體內驗證各種條表達式是否滿足；驗證各種條表達式是否滿足；（5） 根據問題背景，優化程序，以便縮小搜索范根據問題背景，優化程序，以便縮小搜索范圍，減少程序運行時間。圍，減少程序運行時間。【例5】：（百錢買百雞問題）大約在公元5世紀，數學家張邱建在他的算經中提出了一個聞名于后世的百錢百雞問題：雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一，百錢買百雞，翁、母、雛各幾何？1.算法分析與設計(1) 以三種雞的個數為枚舉對象，分別設為x,y,z。根據題意，可以列出下面的不定方程(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有錯誤#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);修改錯誤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次優化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)直接計算出來。在方程（3）中，假設y=0,則x=14,假設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次優化#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】：（誰做的好事）已知有有四位同學中的一位做了好事，不留名，表揚信來了之后，校長問這四位是誰做的好事。A說：不是我。B說：是C。C說：是D。D說：他胡說。已知三個人說的是真話，一個

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

13、an!=A+ thisman=C+ thisman=D+ thisman!=D 那么，cond=3窮舉試探。我們現在并不知道是誰做得好事，但我們知道做好事的人是A,B,C,D四個人中的某一個。因此，我們可以一個一個地試探。先假設是A做的好事，即thisman=A，然后看cond=3條件是否成立，然后再假設是B做的好事，即thisman=B,再測試條件cond=3 是否成立，如此繼續下去，將所有可能的情況（本例自有4種情況）都測試一遍，在實際編程過程中，都是使用循環來一個一個的測試 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】: (四大湖問題)上地理課時，四個學生回答我國四個淡水

15、湖大小時說： A學生：洞庭湖最大，洪澤湖最小，鄱陽湖第3 B學生：洪澤湖最大，洞庭湖最小，鄱陽湖第2，太湖第3 C學生：洪澤湖最小，洞庭湖第3 D學生：鄱陽湖最大，太湖最小，洪澤湖第2，洞庭第3 對于湖的大小，每個學生僅答對一個，請編程判斷四個湖的大小1.分析與算法設計 (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四個變量的取值互不相同，1表示最大，四表最小(2) 用變量表示條件 A學生的敘述可表示為：a=1, b=4,c=3 這是三個關系表達式，由于每個學生

16、的敘述只有一個正確，所以這三個關系表達式的值的和應等于1。 A學生的敘述可表示成： ( (a=1)+(b=4)+(c=3）)=1 同理，B學生的敘述表示成： (b=1)+(a=4)+(c=2)+(d=3)=1 C學生的敘述可表示成： (b=4)+(a=3) =1 D學生的敘述可表示成： (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四個變量的所有可能取值,進行測試，滿足前述四個條件的取值就是我們所要的結果【例8】（白帽子和紅帽子問題）廳內有5個人，他們均戴著帽子白帽子和紅帽子。已知戴白帽子的說真話，戴紅帽子的說假話，請從他們各自提供的線索辨別誰戴白帽子，誰

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

19、他戴的是紅帽子，則他所說的是假話，這樣將每個人帽子顏色與他說的話直接聯系起來，因此上述條件可表示成： 甲：(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) ; 窮舉：對變量a,b,c,d,e的所有可能取值情況進行枚舉，這要用一個5重循環實現。例例9 9：輸入繩子的長度：輸入繩子的長度n n，將該繩子分成三段，每段，將該繩子分成三段，每段的長度為正整數，輸出由該三段繩子組成的三角的長度為正整數，輸出由該三段繩子組成的三角形個數。形個數。 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、問題解的可能搜索的范圍：問題解的可能搜索的范圍： 用循環或循環嵌套結構實現用循環或循環嵌套結構實現 2、寫出符合問題解的條件。寫出符合問題解的條件。 3、能使程序優化的語句，以便縮小搜索范能使程序優化的語句，以便縮小搜索范 圍，減少程序運行時間。圍，減少程

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

23、有紅、橙、黃、綠、藍五種顏色的小球若干，每次隨意摸出三個小球，輸出三個小球顏色都不一樣的所有可能的方案總數。（我承認害了不少人，大家認為：紅、橙、黃 和 橙、紅、黃不一樣吧，這樣就是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: 勾股數 內容：內容：20以內勾股數（假設a=b=c)

24、a2+b2=c2 若有多組，按a從小到大順序輸出 .輸入說明：輸入說明：無輸出說明：輸出說明：一行一組三個數，用空格隔開d058: 勾股數 #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: 倒立勾股數 關鍵字： 內容：內容：1/x2+1/y2=1/z2 其中正整數xyz成為一組倒立的勾股數！注意，是正整數哦！你的任務是輸出60以內的倒立勾股

25、數，按x的的增序輸出（每行一個）。 d071: 倒立勾股數 #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類數 (NOIP1995)內容：內容：若將一個正整數化為二進制數，在此二進制數中，我們將數字1的個數多于數字0的個數的這類二進制數稱為A類數，否則就稱其為B類數。例如：（13）10=（1101）2其中1的個數為3，0的個數為1，則稱此數為A類數；（10）10=（1010）2其中1的個數為2，0的個數也為2，稱此數為B類數；（24）10=（11000）2其中1的個數為2，0的個數為3，則稱此數為B類數；程序要求：