枚舉算法_舉例

1、課前思考 有一個(gè)三位數(shù)x，百位是a，十位是b，個(gè)位是c，x=100*a+10*b+c,利用適當(dāng)?shù)腣B表達(dá)式求出 a= b= c=X mod 10 x10 mod 10 x100 小明是一個(gè)數(shù)學(xué)迷，昨天他約了幾個(gè)同學(xué)小明是一個(gè)數(shù)學(xué)迷，昨天他約了幾個(gè)同學(xué)一起到會(huì)議室里舉行一個(gè)聯(lián)誼會(huì)，可是粗心的一起到會(huì)議室里舉行一個(gè)聯(lián)誼會(huì)，可是粗心的小明去總務(wù)處拿了一串鑰匙回來準(zhǔn)備開門時(shí)，小明去總務(wù)處拿了一串鑰匙回來準(zhǔn)備開門時(shí)，卻忘記了到底哪一把才是會(huì)議室的鑰匙。卻忘記了到底哪一把才是會(huì)議室的鑰匙。假設(shè)假設(shè)這串鑰匙一共有這串鑰匙一共有1010把。把。怎樣才能找到正確的鑰匙來開門怎樣才能找到正確的鑰匙來開門 找鑰匙的

2、過程2.拿出第二把鑰匙，拿出第二把鑰匙， 試驗(yàn)第二把鑰匙能否開門；試驗(yàn)第二把鑰匙能否開門；1.拿出第一把鑰匙，拿出第一把鑰匙， 試驗(yàn)第一把鑰匙能否開門；試驗(yàn)第一把鑰匙能否開門；3.拿出第三把鑰匙，拿出第三把鑰匙， 試驗(yàn)第三把鑰匙能否開門；試驗(yàn)第三把鑰匙能否開門；10.拿出第十把鑰匙，拿出第十把鑰匙， 試驗(yàn)第十把鑰匙能否開門。試驗(yàn)第十把鑰匙能否開門。列舉列舉檢驗(yàn)檢驗(yàn)枚舉法枚舉法枚舉算法枚舉算法就是按照問題本身的性質(zhì)，就是按照問題本身的性質(zhì)，一一列舉一一列舉出該問題所有可能的解，并根據(jù)問題的條件對(duì)各出該問題所有可能的解，并根據(jù)問題的條件對(duì)各解進(jìn)行解進(jìn)行逐個(gè)檢驗(yàn)逐個(gè)檢驗(yàn)，從中挑選出符合條件的解，舍，

3、從中挑選出符合條件的解，舍棄不符合條件的解。棄不符合條件的解。在聯(lián)歡會(huì)上，小明提議大家來玩數(shù)7的游戲。游戲規(guī)則游戲規(guī)則：從1開始數(shù)起，每個(gè)人數(shù)一個(gè)數(shù)， 凡是遇到7的倍數(shù)就要喊“過”, 這樣一直數(shù)到100為止。幫小明找出幫小明找出1100所有要喊所有要喊“過過”的數(shù)的數(shù)列舉列舉檢驗(yàn)檢驗(yàn)用變量用變量i表示要列舉的自然數(shù)。表示要列舉的自然數(shù)。列舉范圍：列舉范圍：1100檢驗(yàn)條件：檢驗(yàn)條件：i能否被能否被7整除。整除。在列舉過程中要既不遺漏，又不重復(fù)。開始開始結(jié)束結(jié)束NNYYi=100i mod 7=0i=i+1i=1輸出輸出i列舉范圍：列舉范圍：1100檢驗(yàn)條件：檢驗(yàn)條件：i能否被能否被7整除。整除

4、。用變量用變量i表示要列舉的自然數(shù)。表示要列舉的自然數(shù)。開始開始結(jié)束結(jié)束NNYYi=100i mod 7=0i=i+1i=1輸出輸出i（循環(huán)結(jié)構(gòu)）（循環(huán)結(jié)構(gòu)）（分支結(jié)構(gòu)）（分支結(jié)構(gòu)）循環(huán)中嵌套分支i=1Do while i=100 if i mod 7=0 then print i end if i=i+1loop開始開始結(jié)束結(jié)束NNYYi=100i mod 7=0i=i+1i=1輸出輸出i枚舉算法的設(shè)計(jì)步驟 確定列舉范圍 明確檢驗(yàn)條件 確定循環(huán)控制方式和列舉方式枚舉算法只適用于可能解的個(gè)數(shù)不太多的情況。 一張單據(jù)上有一個(gè)一張單據(jù)上有一個(gè)5 5位數(shù)的編號(hào)，萬位數(shù)是位數(shù)的編號(hào)，萬位數(shù)是1 1，千

5、位，千位數(shù)是數(shù)是4 4，百位數(shù)是，百位數(shù)是7 7，個(gè)位數(shù)是，個(gè)位數(shù)是8 8，十位數(shù)已經(jīng)模糊不清，十位數(shù)已經(jīng)模糊不清，只知道該，只知道該5 5位數(shù)是位數(shù)是7 7或或1111的倍數(shù)，找出所有滿足這些條的倍數(shù)，找出所有滿足這些條件的件的5 5位數(shù)并輸出。位數(shù)并輸出。 NO. 147 ? 8列舉范圍：列舉范圍：09檢驗(yàn)條件：檢驗(yàn)條件：n能被能被5或者或者11整除。整除。即：即：(n mod 7=0) or (n mod 11=0)用變量用變量i表示十位上的數(shù)；變量表示十位上的數(shù)；變量n表示這個(gè)表示這個(gè)5位數(shù)。位數(shù)。開始開始i=0i10(n mod 7=0) or(n mod 11=0)輸出輸出ni=i

6、+1結(jié)束結(jié)束NNYY程序代碼：程序代碼：i=0Do while i10 n=14708+i*10 if n mod 7=0 or n mod 11=0 then Print n end if i=i+1Loopn=14708+i*10生活中的枚舉算法實(shí)例生活中的枚舉算法實(shí)例 找鑰匙找鑰匙 警察審案警察審案 挑爛蘋果挑爛蘋果1.枚舉算法的概念枚舉算法的概念2.枚舉算法的結(jié)構(gòu)特征枚舉算法的結(jié)構(gòu)特征4.枚舉算法的應(yīng)用枚舉算法的應(yīng)用3.枚舉算法的設(shè)計(jì)步驟枚舉算法的設(shè)計(jì)步驟 一張單據(jù)上有一個(gè)一張單據(jù)上有一個(gè)5 5位數(shù)的編號(hào)，千位數(shù)是位數(shù)的編號(hào)，千位數(shù)是1 1，百位，百位數(shù)是數(shù)是7 7，個(gè)位數(shù)是，個(gè)位數(shù)是

7、8 8，萬位數(shù)和十位數(shù)已經(jīng)模糊不清，只，萬位數(shù)和十位數(shù)已經(jīng)模糊不清，只知道該知道該5 5位數(shù)是位數(shù)是7 7或或1111的倍數(shù)，找出所有滿足這些條件的的倍數(shù)，找出所有滿足這些條件的5 5位數(shù)并輸出。位數(shù)并輸出。 NO. ? 17 ? 8 該題要列舉的對(duì)象有兩個(gè)，分別是萬位數(shù)和個(gè)位數(shù)。用循環(huán)的嵌套。找出找出1-10001-1000中所有能被中所有能被7 7和和1111整除的數(shù)。整除的數(shù)。 c開始結(jié)束TFi=1i=1000i=i+1TF輸出 ii mod 7=0 andi mod 11=0i mod 77=0i mod 3=0雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢雞翁一，值錢五，雞母一，值錢三

8、，雞雛三，值錢一，百錢買百雞，問翁、母、雛各幾何？一，百錢買百雞，問翁、母、雛各幾何？一一列舉：初值：終值：遞增值： a 0 20 1檢驗(yàn)：雞翁雞翁 雞母雞母 雞雛雞雛 b 0 33 1 c 0 100 3a*5+b*3+c/3=100開始TFa=0a=20結(jié)束TFb=0b=33TFc=0c=100TFc=c+3b=b+1a=a+1a*5+b*3+c/3=100輸出 a、b、c求求1-1000中，能被中，能被3整除的數(shù)整除的數(shù)開始結(jié)束TFi=1i=1000i=i+1i mod 3=0TF輸出 ii mod 3=0TF輸出 i檢驗(yàn)檢驗(yàn):枚舉時(shí)注意：不遺漏，不重復(fù)，且可能的解有限。N NY Y輸出

9、輸出X Xx100 x100Y YN NStartStartEndEnd找出所有找出所有100,1000100,1000之間之間3535的倍數(shù)的數(shù)字。的倍數(shù)的數(shù)字。練練 習(xí)習(xí)范圍范圍: :條件：條件：初初 值：值：100100100 100 1000 1000終終 值：值：10001000步步 長：長：1 1x mod 35 = 0 用用1010元和元和5050元兩種紙幣組成元兩種紙幣組成240240元，元，共有幾種組合方式？試用枚舉算法列共有幾種組合方式？試用枚舉算法列出所有不同的取法。出所有不同的取法。練一練10 x+50y=240輸出輸出x,yYx1x1YStartStartNEndEndy 1YNN 用用1010元和元和5050元兩種元兩種紙幣組成紙幣組成240240元，共元，共有幾種組合方式？試有幾種組合方式？試用枚舉算法列出所有用枚舉算法列出所有不同的取法。不同的取法。練一練人有了知識(shí)，就會(huì)具備各種分析能力，明