枚舉算法(課件)

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

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

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ù)開始開始初始初始i1i2008?結束結束i能被能被37整除？整除？輸出輸出iii+1NYNY以上提供的只是一種求被以上提供的只是一種求被37整除的數(shù)的算法，你有沒有更整除的數(shù)的算法，你有沒有更好的算法？好的算法？思思 考：考：枚枚 舉舉 算算 法法 舉舉 例例 問題：一張單據(jù)

4、上有一個5位數(shù)的編號，其百位數(shù)和十位數(shù)已經(jīng)變得模糊不清，如下圖所示，但是知道這個5位數(shù)是37或67的倍數(shù)，現(xiàn)在請你找出所有可能的五位數(shù),并統(tǒng)計這樣數(shù)的個數(shù)？枚枚 舉舉 算算 法法 舉舉 例例 算法：算法：25ab6ab是百位和十位上的數(shù)字，可能的取值是百位和十位上的數(shù)字，可能的取值五位數(shù)五位數(shù)(n)如何表示：如何表示：00-99,故從故從0開始列舉到開始列舉到99n能被能被37或者或者67整除時，就是一個真正解整除時，就是一個真正解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 總計有總計有 + Str(c) + 個五位數(shù)個五位數(shù)n Mod 37 = 0 Or n Mod 67 = 0小結：小結：確定范圍確定范圍情況羅列情況羅列條件判斷條件判斷得到真解得到真解循環(huán)語句循環(huán)語句選擇語句選擇語句用枚舉算法解決問題一般過程用枚舉算法解決問題一般過程:用枚舉算法解決問題須注意以下兩點用枚舉算法解決問題須注意以下兩點:（1）不能遺漏任何一個真正解。）不能遺漏任何一個真正解。（2）縮小搜索范圍，提高效率。）縮小搜索范圍，提高效率。枚舉

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

7、位上可能的數(shù)：09 (i)十位上可能數(shù)數(shù)：09 (j)所以需要兩個循環(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) & 個五位數(shù)人有了知識，就會具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋?！蓖?/p>