枚舉算法課件

枚舉算法枚舉算法1YN開始c←i%10i←i+1結(jié)束i<=999YN輸出ii←100i=a3+b3+c3b←i/10%10a←i/100水仙花數(shù)問題:所謂水仙花數(shù)指的是這樣一些數(shù)：他們的各個(gè)位置上的數(shù)字的立方的和等于它本身，如153=13+53+33，所以153是一個(gè)水仙花數(shù)?，F(xiàn)在要求編程求100-999之間的水仙花數(shù)，并輸出。解題過程:對(duì)于100-999之間的每一個(gè)數(shù),按照水仙花數(shù)的條件逐一進(jìn)行檢驗(yàn)，找到一個(gè)就輸出一個(gè)。YN開始c←i%10i←i+1結(jié)束i<=999YN2什么是枚舉算法枚舉算法就是按照問題本身的性質(zhì)，一一列舉出該問題所有可能的解，并在逐一列舉的過程中，檢驗(yàn)每個(gè)可能解是否是問題的真正解。若是，我們采納這個(gè)解，否則拋棄它。在列舉的過程中，既不能遺漏也不應(yīng)重復(fù)。什么是枚舉算法枚舉算法就是按照問題本身的性質(zhì)，一一列舉出該問3例題：一張單據(jù)上有一個(gè)5位數(shù)的編碼，其千位數(shù)和百位數(shù)已經(jīng)變得模糊不請(qǐng)。但是知道這個(gè)5位數(shù)是57或67的倍數(shù)?，F(xiàn)在要設(shè)計(jì)一個(gè)算法，輸出所有滿足這些條件的5位數(shù)，并統(tǒng)計(jì)這樣的數(shù)的個(gè)數(shù)。No.147例題：一張單據(jù)上有一個(gè)5位數(shù)的編碼，其千位數(shù)和百位數(shù)已經(jīng)變得4分析:首先，千位數(shù)和百位數(shù)可以填上00，01，02，……97，98，99；得到10047，10147，……19947。建一個(gè)循環(huán)變量為j，從0到99的一個(gè)循環(huán)，每一個(gè)可能解n的值為10047+j*100其次，對(duì)每一個(gè)n判斷是否能被57或67整除。若是，輸出一組解，解的個(gè)數(shù)+1；若不是，舍棄分析:首先，千位數(shù)和百位數(shù)可以填上00，5算法描述1、計(jì)數(shù)器c←02、j←03、判斷j<100,是轉(zhuǎn)4，否轉(zhuǎn)向94、可能解n←10047+100*j5、判斷n是否57或67的倍數(shù)，是轉(zhuǎn)向6；否轉(zhuǎn)向86、計(jì)數(shù)器c←c+1；7、輸出真正的解n8、j←j+1；轉(zhuǎn)向39、輸出解的個(gè)數(shù)C10、結(jié)束算法描述1、計(jì)數(shù)器c←06j<100YN開始c←0j←j+1結(jié)束c←c+1輸出nn

←10047+j*100n%57==0或n%67==0NYj←0輸出jj<100YN開始c←0j←j+1結(jié)束c←c+1輸出7采用枚舉算法的條件僅當(dāng)問題的所有可能解不太多的時(shí)候，才可以使用枚舉法。采用枚舉算法的條件僅當(dāng)問題的所有可能解不太多的時(shí)候，才可以使8枚舉法解題過程逐一列舉可能的解逐一檢驗(yàn)可能的解枚舉法解題的難點(diǎn)：1、構(gòu)造循環(huán)2、確定可能的解枚舉法解題過程逐一列舉可能的解枚舉法解題的難點(diǎn)：9例題2：一張單據(jù)上有一個(gè)5位數(shù)的編碼，其千位數(shù)和十位數(shù)已經(jīng)變得模糊不請(qǐng)。但是知道這個(gè)5位數(shù)是57或67的倍數(shù)。現(xiàn)在要設(shè)計(jì)一個(gè)算法，輸出所有滿足這些條件的5位數(shù)，并統(tǒng)計(jì)它們的個(gè)數(shù)。No.147例題2：一張單據(jù)上有一個(gè)5位數(shù)的編碼，其千位數(shù)和十位數(shù)已經(jīng)變10分析：千位數(shù)和十位數(shù)上的數(shù)字只能是0-9中的一個(gè)。10407104171042710437104471045710467104771048710497ij分析：千位數(shù)和十位數(shù)上的數(shù)字只能是0-9中的一個(gè)。101119407194171942719437194471945719467194771948719497iji從0變化到9；j從0變化到9。因此，需要構(gòu)造一個(gè)雙重循環(huán)?？赡艿慕鈔←10407+1000*i+10*j19407194171942719437194471945712雙重循環(huán)的構(gòu)造1、i←02、判斷i<=9；是轉(zhuǎn)向3，否則轉(zhuǎn)向73、j←04、判斷j<=9；是轉(zhuǎn)向5，否則轉(zhuǎn)向65、j←j+1；轉(zhuǎn)向46、i←i+1；轉(zhuǎn)向27、結(jié)束i<=9YN開始i←0i←i+1結(jié)束j<=9Nj←j+1j←0Y雙重循環(huán)的構(gòu)造1、i←0i<=9YN開始i←0i←i13思考：

右面的流程圖有沒有問題i<=9YN開始i←0i←i+1結(jié)束j<=9Nj←j+1j←0Y思考：

右面的流程圖有沒有問題i<=9YN開始i←0i14算法描述1、c←0；i←02、判斷i<=9；是轉(zhuǎn)向3，否則轉(zhuǎn)向113、j←04、判斷j<=9；是轉(zhuǎn)向5，否則轉(zhuǎn)向105、n←10407+1000*i+10*j6、判斷n是否57或67的倍數(shù)，是轉(zhuǎn)向7；否轉(zhuǎn)向97、計(jì)數(shù)器c←c+1；8、輸出一個(gè)真正的解n9、j←j+1；轉(zhuǎn)向410、i←i+1；轉(zhuǎn)向211、輸出解的個(gè)數(shù)c12、結(jié)束算法描述1、c←0；i←015i<=9YN開始i←0i←i+1j<=9Nj←j+1j←0Yc←0c結(jié)束12c←c+1輸出nn

←10047+j*100nmod57=0或nmod67=0NY21i<=9YN開始i←0i←i+1j<=9Nj←j+116例題3百雞百錢問題“雞翁一值錢5，雞母一值錢3，雞雛三值錢1”現(xiàn)有100錢，欲買100只雞，問：雞翁、雞母、雞雛各買幾只？分析：設(shè)x，y，z分別為買的雞翁、雞母、雞雛的個(gè)數(shù)則：x+y+z=1005*x+3*y+z/3=100可能的解X:0-20Y:0-33Z:100-x-y例題3百雞百錢問題分析：17建立一個(gè)雙重循環(huán),可能的解如下：x<=20YN開始x←0x←x+1結(jié)束y<=33Ny←y+1y←0Y判斷可能的解是否是真正的解xyz0010001990298………03367………203347建立一個(gè)雙重循環(huán),可能的解如下：x<=20YN開始x←018檢驗(yàn)可能的解是否真正的解判斷：5*x+3*y+z/3=100若是，x,y,z就是一個(gè)真正的解z←100-x-y輸出x,y,z5*x+3*y+z/3=100NY檢驗(yàn)可能的解是否真正的解判斷：5*x+3*y+z/3=10019例題4包裝問題：600個(gè)變形金剛，包裝的規(guī)格為：大盒（8個(gè)）、中盒（5個(gè)）、小盒（2個(gè)）；每種規(guī)格的盒都不能為空。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，輸出所有可能的包裝方案。分析：設(shè)大中小盒的個(gè)數(shù)分別為x,y,z則：8*x+5*y+2*z=600X：1-74Y：1-118Z：（600-8*x-5*y）/2例題4包裝問題：分析：20算法提示構(gòu)造一個(gè)雙重循環(huán)，循環(huán)變量分別為x（大盒數(shù)量）和y（中盒數(shù)量）。判斷：Z=(600-8*x-5*y)/2是否是整數(shù);若是，則x,y,z就是一個(gè)包裝方案。算法提示構(gòu)造一個(gè)雙重循環(huán)，循環(huán)變量分別為x（大盒數(shù)