枚舉算法(課件)

1、（窮舉算法）（窮舉算法）找找 鑰鑰 匙匙自行車胎壞掉的時(shí)候，修車師傅檢查壞掉的位置，自行車胎壞掉的時(shí)候，修車師傅檢查壞掉的位置，他選定某一個(gè)位置為起始位置，然后按順序一塊塊他選定某一個(gè)位置為起始位置，然后按順序一塊塊的檢查過(guò)來(lái)，直到找到壞掉的位置。的檢查過(guò)來(lái)，直到找到壞掉的位置。找到一個(gè)壞掉的位置后，還要繼續(xù)找嗎？為了安全找到一個(gè)壞掉的位置后，還要繼續(xù)找嗎？為了安全起見(jiàn)，建議繼續(xù)找起見(jiàn)，建議繼續(xù)找討討 論：論：解決以上兩個(gè)實(shí)際生活問(wèn)題時(shí)，主要經(jīng)過(guò)了哪解決以上兩個(gè)實(shí)際生活問(wèn)題時(shí)，主要經(jīng)過(guò)了哪幾個(gè)步驟？幾個(gè)步驟？步驟一、一步驟一、一 一列舉所有可能解一列舉所有可能解步驟二、逐一檢驗(yàn)，不重復(fù)，不遺漏

2、步驟二、逐一檢驗(yàn)，不重復(fù)，不遺漏 按問(wèn)題本身的性質(zhì)，按問(wèn)題本身的性質(zhì)，一一列舉該問(wèn)題所一一列舉該問(wèn)題所有可能的解有可能的解，并在逐一列舉的過(guò)程中，并在逐一列舉的過(guò)程中，檢驗(yàn)檢驗(yàn)每個(gè)可能解是否是問(wèn)題的真正解每個(gè)可能解是否是問(wèn)題的真正解，如是，就，如是，就采納這個(gè)解，否則就拋棄它不重復(fù)，不遺采納這個(gè)解，否則就拋棄它不重復(fù)，不遺漏。漏。枚舉法適合于解的候選者是有限、可列舉的場(chǎng)合。枚舉法適合于解的候選者是有限、可列舉的場(chǎng)合。枚舉法的算法一般都比較直觀，容易理解。枚舉法的算法一般都比較直觀，容易理解。但由于要檢查所有的候選解，因此時(shí)間性能較差。但由于要檢查所有的候選解，因此時(shí)間性能較差。算一算：算一算：

3、 用用10元和元和50元兩種紙幣組成元兩種紙幣組成240元，元，共有幾種組合方式？共有幾種組合方式？（0張50元）24張10元（1張50元）19張10元（2張50元）14張10元（3張50元） 9張10元（4張50元） 4張10元在在1到到2008這些自然數(shù)中，找出所有是這些自然數(shù)中，找出所有是37倍數(shù)的自然數(shù)倍數(shù)的自然數(shù)開(kāi)始開(kāi)始初始初始i1i2008?結(jié)束結(jié)束i能被能被37整除？整除？輸出輸出iii+1NYNY以上提供的只是一種求被以上提供的只是一種求被37整除的數(shù)的算法，你有沒(méi)有更整除的數(shù)的算法，你有沒(méi)有更好的算法？好的算法？思思 考：考：枚枚 舉舉 算算 法法 舉舉 例例 問(wèn)題：一張單據(jù)

4、上有一個(gè)5位數(shù)的編號(hào)，其百位數(shù)和十位數(shù)已經(jīng)變得模糊不清，如下圖所示，但是知道這個(gè)5位數(shù)是37或67的倍數(shù)，現(xiàn)在請(qǐng)你找出所有可能的五位數(shù),并統(tǒng)計(jì)這樣數(shù)的個(gè)數(shù)？枚枚 舉舉 算算 法法 舉舉 例例 算法：算法：25ab6ab是百位和十位上的數(shù)字，可能的取值是百位和十位上的數(shù)字，可能的取值五位數(shù)五位數(shù)(n)如何表示：如何表示：00-99,故從故從0開(kāi)始列舉到開(kāi)始列舉到99n能被能被37或者或者67整除時(shí)，就是一個(gè)真正解整除時(shí)，就是一個(gè)真正解n=25006+ab*10Dim j, n, c As Integer c = 0 List1.Clear For j = 0 To 99 n = 25006 +

5、j * 10 If Then List1.AddItem Str(n) c = c + 1 End If Next j List1.AddItem 總計(jì)有總計(jì)有 + Str(c) + 個(gè)五位數(shù)個(gè)五位數(shù)n Mod 37 = 0 Or n Mod 67 = 0小結(jié)：小結(jié)：確定范圍確定范圍情況羅列情況羅列條件判斷條件判斷得到真解得到真解循環(huán)語(yǔ)句循環(huán)語(yǔ)句選擇語(yǔ)句選擇語(yǔ)句用枚舉算法解決問(wèn)題一般過(guò)程用枚舉算法解決問(wèn)題一般過(guò)程:用枚舉算法解決問(wèn)題須注意以下兩點(diǎn)用枚舉算法解決問(wèn)題須注意以下兩點(diǎn):（1）不能遺漏任何一個(gè)真正解。）不能遺漏任何一個(gè)真正解。（2）縮小搜索范圍，提高效率。）縮小搜索范圍，提高效率。枚舉

6、算法的解題過(guò)程分兩步枚舉算法的解題過(guò)程分兩步 逐一列舉可能的解的范圍。逐一列舉可能的解的范圍。這個(gè)過(guò)程用這個(gè)過(guò)程用循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)實(shí)現(xiàn)實(shí)現(xiàn) 并對(duì)每一個(gè)列舉可能的解進(jìn)行檢驗(yàn)，判斷是否為真正并對(duì)每一個(gè)列舉可能的解進(jìn)行檢驗(yàn)，判斷是否為真正的解的解 。這個(gè)過(guò)程用這個(gè)過(guò)程用選擇結(jié)構(gòu)選擇結(jié)構(gòu)實(shí)現(xiàn)實(shí)現(xiàn) 枚舉算法枚舉算法=循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)+選擇結(jié)構(gòu)選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu)內(nèi)嵌套選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)內(nèi)嵌套選擇結(jié)構(gòu)NO. 2 5 6思考：假如現(xiàn)在這張單據(jù)是千位和十位上的兩個(gè)數(shù)字看不清，這張單據(jù)上的五位數(shù)還是37或67的倍數(shù)，現(xiàn)在要找出所有的可能解，并統(tǒng)計(jì)個(gè)數(shù)。如何解決這個(gè)問(wèn)題？NO. 2 5 6兩個(gè)數(shù)分別在千位和十位上。千

7、位上可能的數(shù)：09 (i)十位上可能數(shù)數(shù)：09 (j)所以需要兩個(gè)循環(huán)變量：i 和jn=20506+i*1000+j*10Dim i, j, n, c As Integer c = 0 For i = 0 To 9 For j = 0 To 9 n = 20506 + i * 1000 + j * 10 If n Mod 37 = 0 Or n Mod 67 = 0 Then Print n c = c + 1 End If Next jNext i Label1.Caption = 總共可能有 & Str(c) & 個(gè)五位數(shù)人有了知識(shí)，就會(huì)具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書(shū)，廣泛閱讀，古人說(shuō)“書(shū)中自有黃金屋。”通