一、窮舉法概述.ppt

《一、窮舉法概述.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、枚舉算法例生活實(shí)例統(tǒng)計(jì)出班級(jí)中感冒的學(xué)生數(shù)流程圖?什么是枚舉算法p21采用“搜索”的方法對(duì)所有可能逐一判斷保留符合要求的解，舍棄不符合要求的?枚舉算法本質(zhì)p21一一“列舉”問題所有可能檢驗(yàn)每個(gè)可能是否是問題的解記錄所有問題解例1算法舉例一張單據(jù)上有一個(gè)5位數(shù)的編號(hào)，其百位和十位數(shù)處已經(jīng)變得模糊不清，但是知道這個(gè)數(shù)是37或67的倍數(shù)?，F(xiàn)在要設(shè)計(jì)一個(gè)算法找出所有滿足這些條件的5位數(shù)，并統(tǒng)計(jì)這些5位數(shù)的個(gè)數(shù)。數(shù)字的推算關(guān)鍵點(diǎn)十位、百位的變化不過是00~99，所以我們可以嘗試所有的可能性，25006、25016、25026……25

2、996看看所有的數(shù)字中哪些能被37或67整除。解題步驟：１.分析問題枚舉所有問題的可能解25xx6，范圍是多少？２.確定方法采用？？結(jié)構(gòu)３.用流程圖表示算法流程圖開始j=0j<=99Yn=25006+j*10n能否被37或者67整除Y輸出j,nj=j+1結(jié)束NNj是十位和百位上的數(shù)十位、百位的變化范圍是00~99代碼：變量的定義：Dimj,nasinteger循環(huán)控制：Forj=0to99n=25006+j*10ifnmod37=0ornmod67=0thenprintj,n開始j=0j<=99Yn=25006+j*10n

3、能否被37或者67整除Y輸出j,nj=j+1結(jié)束NNnextj枚舉法計(jì)算容量比較大，需要優(yōu)化。用鑰匙開門的時(shí)候，當(dāng)鑰匙有一大堆，我們就要首先排除一部分鑰匙孔不一致的鑰匙，從而縮小枚舉范圍，進(jìn)行優(yōu)化。枚舉算法解題過程解題過程分兩步：逐一列舉可能的解的范圍。這個(gè)過程用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)。對(duì)每一個(gè)列舉可能的解進(jìn)行檢驗(yàn)，判斷是否為真正的解。這個(gè)過程用分支結(jié)構(gòu)實(shí)現(xiàn)。枚舉算法=循環(huán)結(jié)構(gòu)+分支結(jié)構(gòu)，循環(huán)結(jié)構(gòu)內(nèi)嵌套選擇結(jié)構(gòu)課堂總結(jié)1.枚舉算法=循環(huán)結(jié)構(gòu)+分支結(jié)構(gòu)2.做到既不遺漏任何一個(gè)解、也不重復(fù).3.枚舉算法效率較低.注：并不是所有的問題都可

4、以使用枚舉算法來求解，只有當(dāng)問題的所有可能解的個(gè)數(shù)不太多時(shí)，并在可以接受的時(shí)間內(nèi)得到問題的所有解，才有可能使用枚舉算法。作業(yè)：編程序求100以內(nèi)所有的素?cái)?shù)的和。（提示：素?cái)?shù)是指除了能被1和其本身整除以外，其他數(shù)都不能被整除。）