研究生課程-算法設(shè)計(jì)與分析之枚舉算法

算法設(shè)計(jì)與分析北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院

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

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

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

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

解的高準(zhǔn)確性和全面性實(shí)現(xiàn)簡(jiǎn)單，枚舉算法通過循環(huán)來逐一列舉和驗(yàn)證可能解效率提升空間比較大枚舉三步確定枚舉對(duì)象枚舉對(duì)象也可以理解為是問題解的表達(dá)形式，一般需要用若干參數(shù)來描述參數(shù)之間需要相互獨(dú)立，而且，參數(shù)數(shù)目越少，問題解的搜索空間的維度也相應(yīng)地?。幻總€(gè)參數(shù)的取值范圍越小，問題解的搜索空間也越小。逐一列舉可能解根據(jù)枚舉對(duì)象的參數(shù)構(gòu)造循環(huán)，一一列舉其表達(dá)式的每一種取值情況。逐一驗(yàn)證可能解根據(jù)問題解的要求，一一驗(yàn)證枚舉對(duì)象表達(dá)式的每一個(gè)取值，如果滿足條件，則采納它，否則，拋棄之。模糊數(shù)字任務(wù)描述：一張單據(jù)上有一個(gè)5位數(shù)的編碼，因?yàn)楸９懿簧?，其百位?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ù)。輸入：每一行對(duì)應(yīng)一個(gè)測(cè)試樣例，每一行包含4個(gè)數(shù)字，依次是萬位數(shù)，千位數(shù)，十位數(shù)和個(gè)位數(shù)。最后一行包含4個(gè)-1，表示輸入結(jié)束。輸出：每組測(cè)試樣例的結(jié)果輸出占一行，第一個(gè)數(shù)字表示滿足條件的編碼個(gè)數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字與數(shù)字之間用空格隔開。19？95模糊數(shù)字枚舉對(duì)象

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

=0～9逐一列舉

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

19h95能否整除57和67模糊數(shù)字續(xù)任務(wù)描述：一張單據(jù)上有一個(gè)5位數(shù)的編碼，因?yàn)楸９懿簧疲淙f位數(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ù)。輸入：每一行對(duì)應(yīng)一個(gè)測(cè)試樣例，每一行包含3個(gè)數(shù)字，依次是千位數(shù)，十位數(shù)和個(gè)位數(shù)。最后一行包含3個(gè)-1，表示輸入結(jié)束。輸出：每組測(cè)試樣例的結(jié)果輸出占一行，第一個(gè)數(shù)字表示滿足條件的編碼個(gè)數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字與數(shù)字之間用空格隔開。？9？95模糊數(shù)字續(xù)枚舉對(duì)象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++)逐一驗(yàn)證

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

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

n1+

n2+

n3==n,5n1+

3n2+

n3/3

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

-n2逐一列舉

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

3n2+

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

=

{輕，重，真}逐一列舉逐一驗(yàn)證“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不可能為重的假幣；判斷比真幣輕判斷比真幣重課后思考題題一：給一個(gè)很長(zhǎng)的數(shù)字串S：123456891011121314…，它是由所有的自然數(shù)從小到大依次排列起來的。任意給一個(gè)數(shù)字串S1(其長(zhǎng)度不大于10)，求出S1在S中第一次出現(xiàn)的位置。比如：輸入101，輸出為10考慮：2132課后思考題題二：形如ax3+bx2+cx+d=0

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