1、小越中學信息技術(shù)組第二章 算法實例 2.1枚舉算法一、作業(yè)回顧表揚：張嫻雯孫瑩、黃豪炳A、B兩數(shù)交換問題：（借用第三者）方法一：CA：AB：BC（加減法）方法二：AA+B：BAB：AAB（非零乘除法）方法三：AA+B：BAB：AAB4、稱鹽問題1、左邊放1、1、2、5法碼，共9克2、右邊放9克食鹽3、拿掉法碼，將食鹽平分，即得5、判斷構(gòu)成三解形開始輸入三邊a,b,c11a+b=ca+c=bb+c0?負數(shù)sum2=sum2+nc2=c2+1YNYN想一想： 一天早上，數(shù)學課代表收好了數(shù)學練習本，他的同桌物理課代表收好了物理練習本，但是由于一些意外，兩種練習本混在了一起。現(xiàn)在要把混在一起的74本練

2、習本區(qū)分開，假如你是數(shù)學課代表，你會怎么做？ 請講出你的解決方案。C=74Y列舉檢驗是否繼續(xù)列舉YNC=C+1打開一本作業(yè)是數(shù)學作業(yè)嗎放在左邊放在右邊YNC=1N試一試： 請用自己的話試著總結(jié)什么是枚舉法。這種列舉出所有可能的情況并逐一進行檢驗，根據(jù)檢驗的結(jié)果執(zhí)行相應(yīng)操作的方法就是枚舉法。枚舉法的基本思想：是根據(jù)提出的問題枚舉所有可能狀態(tài)，并用問題給定的條件檢驗?zāi)男┦欠蠗l件的，哪些是不符合條件的，去掉。能使命題成立，即為其解。其實質(zhì)是一一列舉所有可能，過濾掉不合要求，保留符合要求。枚舉法的優(yōu)點：由于枚舉算法一般是現(xiàn)實生活中問題的“直譯”，因此比較直觀，易于理解；由于枚舉算法建立在考察大量狀態(tài)

3、、甚至是窮舉所有狀態(tài)的基礎(chǔ)上，所以算法的正確性比較容易證明。枚舉法的缺點： 枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量以及單個狀態(tài)枚舉的代價，因此效率比較低。練一練： 學校體育館買進100個籃球，只有“斯伯丁”和“摩騰”兩個牌子，為運輸方便將它們混在了一起運來。請你設(shè)計一個算法，幫助器材保管員統(tǒng)計共有多少個“斯伯丁”籃球。 要求： 請將你解決問題的流程圖繪制出來。 開始J=100C=0,J=1YNN輸出C結(jié)束拿出一個籃球是斯伯丁嗎C=C+1Y列舉檢驗J=J+1研究范圍列舉檢驗是否繼續(xù)列舉YN枚舉法的結(jié)構(gòu)特點：逐一列舉和檢驗，用逐一列舉和檢驗，用循環(huán)結(jié)構(gòu)實現(xiàn)循環(huán)結(jié)構(gòu)實現(xiàn)。關(guān)鍵步驟：確定范圍、列舉、檢驗。

4、 檢驗就是對某個給定的條件進行判斷，根據(jù)判斷的不同結(jié)果執(zhí)行不同操作，所以檢驗可用分支結(jié)構(gòu)實現(xiàn)。是數(shù)學作業(yè)嗎放在左邊放在右邊YN 若一個三位數(shù)X=100a+10b+c（a、b、c都是個位數(shù)），滿足a3+b3+c3=X,則X稱為水仙花數(shù)，請設(shè)計算法，找出所有的水仙花數(shù)。 列舉檢驗研究范圍100 = X = 999分別得到三位數(shù)的百位a、十位b、個位ca3+b3+c3=X開始結(jié)束X=100X=999分別得到三位數(shù)的百位a、十位b、個位ca3+b3+c3=X輸出XX=X+1a=int(X/100)c=X % 10b=(X-100*a-c)/10YYNN枚舉法的注意點：1、選定合適的研究對象的范圍。2、

5、找到判斷正確解的條件，列舉。3、逐一檢驗范圍內(nèi)的所有研究對象。例1：涂抹數(shù)字一張單據(jù)上有一個一張單據(jù)上有一個5 5位數(shù)的編碼，其千位數(shù)和百位數(shù)已經(jīng)變得位數(shù)的編碼，其千位數(shù)和百位數(shù)已經(jīng)變得模糊不請。但是知道這個模糊不請。但是知道這個5 5位數(shù)是位數(shù)是5757或或6767的倍數(shù)。現(xiàn)在要設(shè)計的倍數(shù)。現(xiàn)在要設(shè)計一個算法，輸出所有滿足這些條件的一個算法，輸出所有滿足這些條件的5 5位數(shù)，并統(tǒng)計這樣的數(shù)位數(shù)，并統(tǒng)計這樣的數(shù)的個數(shù)。的個數(shù)。No.No.1 47分析分析:范范圍圍：首先首先，千位，千位數(shù)數(shù)和百位和百位數(shù)數(shù) 可以可以填填上上0000，0101，0202，9797，9898，9999；得到；得到1

6、004710047，1014710147，1994719947。建一。建一個個循循環(huán)變環(huán)變量量為為j j，從從0 0到到9999的一的一個個循循環(huán)環(huán)，每一，每一個個可能解可能解n n的的值為值為10047+j10047+j* *100100列列舉舉：其次其次，對對每一每一個個n n判判斷斷是否能被是否能被5757或或6767整除。若是，整除。若是，輸輸出一出一組組解，解的解，解的個數(shù)個數(shù)+1+1；若不是，；若不是，舍棄舍棄檢驗檢驗：n mod 57=0 or n mod 67=0 n mod 57=0 or n mod 67=0 ( (其他判其他判斷斷方法）方法）算法描述算法描述1、計數(shù)器c0

7、02 2、j0j03 3、判斷、判斷j100,j100,是轉(zhuǎn)是轉(zhuǎn)4 4，否轉(zhuǎn)向，否轉(zhuǎn)向 9 94 4、可能解、可能解 n10047+100n10047+100* *j j5 5、判斷、判斷n n是否是否5757或或6767的倍數(shù)，是的倍數(shù)，是轉(zhuǎn)向轉(zhuǎn)向6 6；否轉(zhuǎn)向；否轉(zhuǎn)向8 86 6、計數(shù)器、計數(shù)器c cc+1c+1；7 7、輸出真正的解、輸出真正的解n n8 8、j jj+1j+1；轉(zhuǎn)向；轉(zhuǎn)向 3 39 9、輸出解的個數(shù)、輸出解的個數(shù) C C1010、結(jié)束、結(jié)束j100YN開始開始c 0 j j+1結(jié)束結(jié)束c c+1輸出輸出 nn 10047+j*100 n mod 57=0或或n mod

8、67=0NYj 0 輸出輸出 j上虞區(qū)小越中學信息技術(shù)組編寫程序深化思考題：一張單據(jù)上有一個5位數(shù)的編碼，其千位數(shù)和十位數(shù)已經(jīng)變得模糊不請。但是知道這個5位數(shù)是57或67的倍數(shù)。現(xiàn)在要設(shè)計一個算法，輸出所有滿足這些條件的5位數(shù)，并統(tǒng)計它們的個數(shù)。No.No.1 4 7范范圍圍：雞翁列列舉舉：x=20YN開始開始x 0 x x+1結(jié)束結(jié)束y=33Ny y+1y 0 Yxyz0010001990298 0336720 3347z 100-x-y輸出輸出x,y,z5*x+3*y+z/3=100NY范范圍圍： 列列舉舉： 檢驗檢驗：x=74YN開始開始x 1 x x+1y=200Ny y+1y 1 結(jié)

9、束結(jié)束Yx*8+y*3=600?輸出x,y值假如要求：1、大盒是偶數(shù)的呢？2、大盒數(shù)量要超過小盒的數(shù)量深化思考題思考題： 如果你是體育委員，假設(shè)為了教學的需要，要對總共60個籃球進行分組。要求如下： 1、A類組每組有4個球，B類組每組有6個球； 2、A類組和B類組的數(shù)量都不能為0。請設(shè)計一個算法，輸出所有可能的分組方案。 開始A=1A=14B=1B=10A*4+B*6=50輸出A,BB=B+1A=A+1結(jié)束NYYNYNP251、2、3題作業(yè)：分析：分析： 千位數(shù)和十位數(shù)上的數(shù)字只能是0-9中的一個。104071041710427104371044710457104671047710487104

10、97ij19407194171942719437194471945719467194771948719497iji 從從0變化到變化到9；j從從0變化變化到到9。因此，需要構(gòu)造一。因此，需要構(gòu)造一個雙重循環(huán)。個雙重循環(huán)。可能的解可能的解n 10407+1000*i+10*j雙重循環(huán)的構(gòu)造雙重循環(huán)的構(gòu)造1、i 02、判斷、判斷i=9；是轉(zhuǎn)向；是轉(zhuǎn)向3，否則轉(zhuǎn)向否則轉(zhuǎn)向73、j 04、判斷、判斷j=9；是轉(zhuǎn)向；是轉(zhuǎn)向5，否則轉(zhuǎn)向否則轉(zhuǎn)向65、j j+1； 轉(zhuǎn)向轉(zhuǎn)向46、i i+1；轉(zhuǎn)向；轉(zhuǎn)向27、結(jié)束、結(jié)束i=9YN開始開始i 0 i i+1結(jié)束結(jié)束j=9Nj j+1j 0 Y思考：思考：右面的流程右面的流程圖有沒有問圖有沒有問題題i=9YN開始開始i 0 i i+1結(jié)束結(jié)束j=9Nj j+1j 0 Y算法描述j+1；轉(zhuǎn)向 410、i i+1；轉(zhuǎn)向 2i=9YN開始開始i 0 i i+1j=9Nj j+