研究生課程-算法設計與分析之枚舉算法

算法設計與分析北京交通大學計算機與信息技術學院

李清勇E-mail:qingyongli@Tel:51688603主校區(qū):9號樓北314課前面試找出“水仙花數(shù)”“水仙花數(shù)”是一個神奇的3位數(shù)，其各位數(shù)字立方和等于該數(shù)本身。例如，153就是一水仙花數(shù)。怎樣找出所有的“水仙花數(shù)”？3位數(shù)（100～999）各位數(shù)字立方和等于該數(shù)本身課前面試猴子分桃五只猴子一起摘了一堆桃子，因為太累了，它們商量決定，先睡一覺再分。一會其中的一只猴子來了，它見別的猴子沒來，便將這堆桃子平均分成5份

，結(jié)果多了一個，就將多的這個吃了，并拿走其中的一份。一會兒，第2只猴子來了，他不知道已經(jīng)有一個同伴來過，還以為自己是第一個到的呢，于是將地上的桃子堆起來，再一次平均分成5份，發(fā)現(xiàn)也多了一個，同樣吃了這1個，并拿走其中一份。接著來的第3、第4、第5只猴子都是這樣做的……根據(jù)上面的條件，問這5只猴子至少摘了多少個桃子?第5只猴子走后還剩下多少個桃子?

枚舉算法基本思想枚舉算法也稱之為窮舉算法，就是按照問題本身的性質(zhì)，一一列舉出該問題所有可能的解，并在列舉的過程中，逐一檢驗每個可能解是否是問題的真正解。若是，則采納這個解；否則拋棄它。

不能遺漏不要重復枚舉算法基本思想枚舉算法也稱之為窮舉算法，就是按照問題本身的性質(zhì)，一一列舉出該問題所有可能的解，并在列舉的過程中，逐一檢驗每個可能解是否是問題的真正解。若是，則采納這個解；否則拋棄它。

解的高準確性和全面性實現(xiàn)簡單，枚舉算法通過循環(huán)來逐一列舉和驗證可能解效率提升空間比較大枚舉三步確定枚舉對象枚舉對象也可以理解為是問題解的表達形式，一般需要用若干參數(shù)來描述參數(shù)之間需要相互獨立，而且，參數(shù)數(shù)目越少，問題解的搜索空間的維度也相應地??；每個參數(shù)的取值范圍越小，問題解的搜索空間也越小。逐一列舉可能解根據(jù)枚舉對象的參數(shù)構(gòu)造循環(huán)，一一列舉其表達式的每一種取值情況。逐一驗證可能解根據(jù)問題解的要求，一一驗證枚舉對象表達式的每一個取值，如果滿足條件，則采納它，否則，拋棄之。模糊數(shù)字任務描述：一張單據(jù)上有一個5位數(shù)的編碼，因為保管不善，其百位數(shù)已經(jīng)變得模糊不請。但是知道這個5位數(shù)是57和67的倍數(shù)?，F(xiàn)在要設計一個算法，輸出所有滿足這些條件的5位數(shù)，并統(tǒng)計這樣的數(shù)的個數(shù)。輸入：每一行對應一個測試樣例，每一行包含4個數(shù)字，依次是萬位數(shù)，千位數(shù)，十位數(shù)和個位數(shù)。最后一行包含4個-1，表示輸入結(jié)束。輸出：每組測試樣例的結(jié)果輸出占一行，第一個數(shù)字表示滿足條件的編碼個數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字與數(shù)字之間用空格隔開。19？95模糊數(shù)字枚舉對象

Obj(h)：記h百位數(shù)數(shù)字，h

=0～9逐一列舉

for(h=0;h<10;h++)逐一驗證

19h95能否整除57和67模糊數(shù)字續(xù)任務描述：一張單據(jù)上有一個5位數(shù)的編碼，因為保管不善，其萬位數(shù)字和百位數(shù)已經(jīng)變得模糊不請。但是知道這個5位數(shù)是57和67的倍數(shù)?，F(xiàn)在要設計一個算法，輸出所有滿足這些條件的5位數(shù)，并統(tǒng)計這樣的數(shù)的個數(shù)。輸入：每一行對應一個測試樣例，每一行包含3個數(shù)字，依次是千位數(shù)，十位數(shù)和個位數(shù)。最后一行包含3個-1，表示輸入結(jié)束。輸出：每組測試樣例的結(jié)果輸出占一行，第一個數(shù)字表示滿足條件的編碼個數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字與數(shù)字之間用空格隔開。？9？95模糊數(shù)字續(xù)枚舉對象obj(d1,d2)萬位數(shù)數(shù)字，記為d1，d1=1～9百位數(shù)數(shù)字，記為d2，d2=0～9逐一列舉

for(d1=1;d1<10;d1++)for(d2=0;d2<10;d2++)逐一驗證

d19d295能否整除57和67模糊數(shù)字再續(xù)任務描述：一張單據(jù)上有一個5位數(shù)的編碼，因為保管不善，其萬位數(shù)字和千位數(shù)已經(jīng)變得模糊不請。但是知道這個5位數(shù)是57和67的倍數(shù)?，F(xiàn)在要設計一個算法，輸出所有滿足這些條件的5位數(shù)，并統(tǒng)計這樣的數(shù)的個數(shù)。輸入：每一行對應一個測試樣例，每一行包含3個數(shù)字，依次是百位數(shù)，十位數(shù)和個位數(shù)。最后一行包含3個-1，表示輸入結(jié)束。輸出：每組測試樣例的結(jié)果輸出占一行，第一個數(shù)字表示滿足條件的編碼個數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字與數(shù)字之間用空格隔開。？？095m錢n雞任務描述：我國古代數(shù)學家張丘建在《算經(jīng)》中出了一道題“雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、雞母、雞雛各幾何？”，現(xiàn)在假定各雞種的價格不變，擁有的錢數(shù)為m，需要購買的雞數(shù)為n，試求出所有可能的購買方案總數(shù)。輸入：每行對應一個測試樣例，每一行包含2個數(shù)字，分別為n和m。最后一行包含2個-1，表示輸入結(jié)束。輸出：每組測試樣例的結(jié)果輸出占一行，輸出可能購買方案總數(shù)。m錢n雞枚舉對象obj(n1，n2，n3)雞翁數(shù)，記為n1，n1=0～n雞母數(shù)，記為n2，n2=0～n雞雛數(shù)，記為n3，n3=0～n逐一列舉

三層for循環(huán)嵌套逐一驗證

n1+

n2+

n3==n,5n1+

3n2+

n3/3

==mm錢n雞-改進枚舉對象obj(n1，n2)雞翁數(shù)，記為n1，n1=0～m/5雞母數(shù)，記為n2，n2=0～m/3雞雛數(shù)，記為n3，n3=n-n1

-n2逐一列舉

二層for循環(huán)嵌套逐一驗證5n1+

3n2+

n3/3==m算法復雜度O(m^2)真假銀幣任務描述：張三有12枚銀幣，其中有11枚真幣和1枚假幣。假幣看起來和真幣完全一樣，但是他們的重量不一樣。很遺憾的是，張三不知道假幣比真幣輕還是重。但是他辦公室有一架天平，還有一個聰明的助手。經(jīng)過精心安排每次的稱重，助手保證在稱3次后確定發(fā)現(xiàn)假幣。助手想跟張三開一個小小的玩笑，只告訴他每次稱重的方案和天平的狀態(tài)，但是不告訴他哪個是假幣，假幣比真幣輕還是重。請設計一個算法幫張三辨別真假銀幣。輸入：第一行包含一個正整數(shù)，表示測試數(shù)據(jù)的組數(shù)。每組測試數(shù)據(jù)有三行，每行表示一次稱重的結(jié)果。張三和助手事先把銀幣標號為A～L。每次稱重的結(jié)果用3個以空格隔開的字符串表示：天平左邊放置的銀幣標號，天平右邊放置的銀幣標號，以及平衡狀態(tài)。其中平衡狀態(tài)用“up”、“down”和“even”表示，分別表示右端高、右端低和平衡。另外，每次稱重天平左右的銀幣數(shù)總是相等的。輸出：每組測試數(shù)據(jù)的輸出占一行，輸出假銀幣的標號，并指明它比真幣輕還是重，請則輸出light，重則輸出heavy。真假銀幣輸入樣例：1ABCDEFGHevenABCIEFJKupABIJEFGHeven輸出樣例：Klight真假銀幣枚舉對象obj(c,s)c為銀幣標號，c=A～Ls為銀幣性質(zhì)，s

=

{輕，重，真}逐一列舉逐一驗證“Even”狀態(tài),天平任意一端出現(xiàn)s,則s不可能為輕的假幣；“Up”狀態(tài),天平右端沒有出現(xiàn)s,則s不可能為輕的假幣；“Down”狀態(tài),天平左端沒有出現(xiàn)s,則s不可能為輕的假幣；“Even”狀態(tài),天平任意一端出現(xiàn)s,則s不可能為重的假幣；“Up”狀態(tài),天平左端沒有出現(xiàn)s,則s不可能為重的假幣；“Down”狀態(tài),天平右端沒有出現(xiàn)s,則s不可能為重的假幣；判斷比真幣輕判斷比真幣重課后思考題題一：給一個很長的數(shù)字串S：123456891011121314…，它是由所有的自然數(shù)從小到大依次排列起來的。任意給一個數(shù)字串S1(其長度不大于10)，求出S1在S中第一次出現(xiàn)的位置。比如：輸入101，輸出為10考慮：2132課后思考題題二：形如ax3+bx2+cx+d=0

的一個一元三次方程。給出該方程中各項的系數(shù)(a，b，c，d