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

1、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 李清勇李清勇E-mail: Tel: 51688603主校區(qū): 9號(hào)樓 北314課前面試o 找出找出“水仙花數(shù)水仙花數(shù)” “水仙花數(shù)”是一個(gè)神奇的3位數(shù)，其各位數(shù)字立方和等于該數(shù)本身。例如，153就是一水仙花數(shù)。 怎樣找出所有的“水仙花數(shù)”？ 3位數(shù)（100999） 各位數(shù)字立方和等于該數(shù)本身課前面試p 猴子分桃猴子分桃五只猴子一起摘了一堆桃子，因?yàn)樘哿?，它們商量決定，先睡一覺(jué)再分。一會(huì)其中的一只猴子來(lái)了，它見(jiàn)別的猴子沒(méi)來(lái)，便將這堆桃子平均分成5份 ，結(jié)果多了一個(gè)，就將多的這個(gè)吃了，并拿走其中的一份。一會(huì)兒，第2只猴子來(lái)了，他不知

2、道已經(jīng)有一個(gè)同伴來(lái)過(guò)，還以為自己是第一個(gè)到的呢，于是將地上的桃子堆起來(lái)，再一次平均分成5份，發(fā)現(xiàn)也多了一個(gè)，同樣吃了這1個(gè)，并拿走其中一份。接著來(lái)的第3、第4、第5只猴子都是這樣做的根據(jù)上面的條件，問(wèn)這5只猴子至少摘了多少個(gè)桃子?第5只猴子走后還剩下多少個(gè)桃子? 枚舉算法基本思想o 枚舉算法枚舉算法 也稱(chēng)之為窮舉算法，就是按照問(wèn)題本身的性質(zhì)，一一一一列舉出該問(wèn)題所有可能的解列舉出該問(wèn)題所有可能的解，并在列舉的過(guò)程中，逐一逐一檢驗(yàn)每個(gè)可能解是否是問(wèn)題的真正解檢驗(yàn)每個(gè)可能解是否是問(wèn)題的真正解。若是，則采納這個(gè)解；否則拋棄它。 不能遺漏不能遺漏 不要重復(fù)不要重復(fù)枚舉算法基本思想o 枚舉算法枚舉算法

3、也稱(chēng)之為窮舉算法，就是按照問(wèn)題本身的性質(zhì)，一一一一列舉出該問(wèn)題所有可能的解列舉出該問(wèn)題所有可能的解，并在列舉的過(guò)程中，逐一逐一檢驗(yàn)每個(gè)可能解是否是問(wèn)題的真正解檢驗(yàn)每個(gè)可能解是否是問(wèn)題的真正解。若是，則采納這個(gè)解；否則拋棄它。 解的高準(zhǔn)確性和全面性解的高準(zhǔn)確性和全面性 實(shí)現(xiàn)簡(jiǎn)單，枚舉算法通過(guò)循環(huán)來(lái)逐一列舉和驗(yàn)證可能解實(shí)現(xiàn)簡(jiǎn)單，枚舉算法通過(guò)循環(huán)來(lái)逐一列舉和驗(yàn)證可能解 效率提升空間比較大效率提升空間比較大 枚舉三步o確定枚舉對(duì)象確定枚舉對(duì)象 枚舉對(duì)象也可以理解為是問(wèn)題解的表達(dá)形式，一般需要用若干參數(shù)來(lái)描述一般需要用若干參數(shù)來(lái)描述o參數(shù)之間需要相互獨(dú)立，而且，參數(shù)數(shù)目越少，問(wèn)題解的搜索空間的維度也相應(yīng)

4、地??；o每個(gè)參數(shù)的取值范圍越小，問(wèn)題解的搜索空間也越小。逐一列舉可能解逐一列舉可能解 根據(jù)枚舉對(duì)象的參數(shù)構(gòu)造循環(huán)構(gòu)造循環(huán)，一一列舉其表達(dá)式的每一種取值情況。逐一驗(yàn)證可能解逐一驗(yàn)證可能解 根據(jù)問(wèn)題解的要求，一一驗(yàn)證一一驗(yàn)證枚舉對(duì)象表達(dá)式的每一個(gè)取值，如果滿足條件，則采納它，否則，拋棄之。模糊數(shù)字任務(wù)描述任務(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ù)字，依次是萬(wàn)位數(shù)，千位數(shù)，十位數(shù)和個(gè)位數(shù)。最后一行包含4

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

6、字，依次是千位數(shù)，十位數(shù)和個(gè)位數(shù)。最后一行包含3個(gè)-1，表示輸入結(jié)束。o 輸出：輸出：每組測(cè)試樣例的結(jié)果輸出占一行，第一個(gè)數(shù)字表示滿足條件的編碼個(gè)數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字與數(shù)字之間用空格隔開(kāi)。 ？9？95模糊數(shù)字續(xù)o 枚舉對(duì)象obj(d1,d2)萬(wàn)位數(shù)數(shù)字，記為d1，d1=19百位數(shù)數(shù)字，記為d2， d2 =09o 逐一列舉 for(d1=1;d110;d1+) for(d2=0;d210;d2+)o 逐一驗(yàn)證 d1 9 d2 95能否整除57和67模糊數(shù)字再續(xù)o 任務(wù)描述：任務(wù)描述：一張單據(jù)上有一個(gè)5位數(shù)的編碼，因?yàn)楸９懿簧疲淙f(wàn)位數(shù)字萬(wàn)位數(shù)字和千位數(shù)千位數(shù)已經(jīng)變得模糊不請(qǐng)

7、。但是知道這個(gè)5位數(shù)是57和67的倍數(shù)?，F(xiàn)在要設(shè)計(jì)一個(gè)算法，輸出所有滿足這些條件的5位數(shù)，并統(tǒng)計(jì)這樣的數(shù)的個(gè)數(shù)。o 輸入：輸入：每一行對(duì)應(yīng)一個(gè)測(cè)試樣例，每一行包含3個(gè)數(shù)字，依次是百位數(shù)，十位數(shù)和個(gè)位數(shù)。最后一行包含3個(gè)-1，表示輸入結(jié)束。o 輸出：輸出：每組測(cè)試樣例的結(jié)果輸出占一行，第一個(gè)數(shù)字表示滿足條件的編碼個(gè)數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字與數(shù)字之間用空格隔開(kāi)。 ？095m錢(qián)n雞o 任務(wù)描述任務(wù)描述：我國(guó)古代數(shù)學(xué)家張丘建在算經(jīng)中出了一道題“雞翁一，值錢(qián)五；雞母一，值錢(qián)三；雞雛三，值錢(qián)一。百錢(qián)買(mǎi)百雞，問(wèn)雞翁、雞母、雞雛各幾何？”，現(xiàn)在假定各雞種的價(jià)格不變，擁有的錢(qián)數(shù)為m，需要購(gòu)買(mǎi)的

8、雞數(shù)為n，試求出所有可能的購(gòu)買(mǎi)方案總數(shù)。o 輸入輸入：每行對(duì)應(yīng)一個(gè)測(cè)試樣例，每一行包含2個(gè)數(shù)字，分別為n 和m 。最后一行包含2個(gè)-1，表示輸入結(jié)束。o 輸出輸出：每組測(cè)試樣例的結(jié)果輸出占一行，輸出可能購(gòu)買(mǎi)方案總數(shù)。m錢(qián)n雞o 枚舉對(duì)象obj(n1， n2， n3)雞翁數(shù)，記為n1， n1= 0n雞母數(shù)，記為n2， n2 = 0n雞雛數(shù)，記為n3， n3 = 0no 逐一列舉 三層for循環(huán)嵌套o(hù) 逐一驗(yàn)證 n1+ n2+ n3=n, 5n1+ 3n2+ n3 /3 =mm錢(qián)n雞-改進(jìn)o 枚舉對(duì)象obj(n1， n2)雞翁數(shù)，記為n1， n1= 0m/5雞母數(shù)，記為n2， n2 = 0m/3雞

9、雛數(shù)，記為n3， n3 = n- n1 - n2o 逐一列舉 二層for循環(huán)嵌套o(hù) 逐一驗(yàn)證 5n1+ 3n2+ n3 /3=m算法復(fù)雜度O(m2)真假銀幣o任務(wù)描述：任務(wù)描述：張三有12枚銀幣，其中有11枚真幣和1枚假幣。假幣看起來(lái)和真幣完全一樣，但是他們的重量不一樣。很遺憾的是，張三不知道假幣比真幣輕還是重。但是他辦公室有一架天平，還有一個(gè)聰明的助手。經(jīng)過(guò)精心安排每次的稱(chēng)重，助手保證在稱(chēng)3次后確定發(fā)現(xiàn)假幣。助手想跟張三開(kāi)一個(gè)小小的玩笑，只告訴他每次稱(chēng)重的方案和天平的狀態(tài)，但是不告訴他哪個(gè)是假幣，假幣比真幣輕還是重。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法幫張三辨別真假銀幣。o輸入：輸入：第一行包含一個(gè)正整數(shù)，表示測(cè)

10、試數(shù)據(jù)的組數(shù)。每組測(cè)試數(shù)據(jù)有三行，每行表示一次稱(chēng)重的結(jié)果。張三和助手事先把銀幣標(biāo)號(hào)為AL。每次稱(chēng)重的結(jié)果用3個(gè)以空格隔開(kāi)的字符串表示：天平左邊放置的銀幣標(biāo)號(hào)，天平右邊放置的銀幣標(biāo)號(hào)，以及平衡狀態(tài)。其中平衡狀態(tài)用“up”、“down”和“even”表示，分別表示右端高、右端低和平衡。另外，每次稱(chēng)重天平左右的銀幣數(shù)總是相等的。o輸出：輸出：每組測(cè)試數(shù)據(jù)的輸出占一行，輸出假銀幣的標(biāo)號(hào)，并指明它比真幣輕還是重，請(qǐng)則輸出 light，重則輸出 heavy。 真假銀幣o 輸入樣例：輸入樣例：1ABCD EFGH evenABCI EFJK upABIJ EFGH eveno 輸出樣例：輸出樣例：K lig

11、ht真假銀幣o 枚舉對(duì)象obj(c, s)c 為銀幣標(biāo)號(hào)， c = ALs 為銀幣性質(zhì)， s = 輕，重，真o 逐一列舉o 逐一驗(yàn)證“Even”狀態(tài),天平任意一端出現(xiàn)s,則s不可能為輕的假幣；“Up”狀態(tài),天平右端沒(méi)有出現(xiàn)右端沒(méi)有出現(xiàn)s s,則s不可能為輕的假幣；“Down”狀態(tài),天平左端沒(méi)有出現(xiàn)左端沒(méi)有出現(xiàn)s s,則s不可能為輕的假幣；“Even”狀態(tài),天平任意一端出現(xiàn)s,則s不可能為重的假幣；“Up”狀態(tài),天平左端沒(méi)有出現(xiàn)左端沒(méi)有出現(xiàn)s s,則s不可能為重的假幣；“Down”狀態(tài),天平右端沒(méi)有出現(xiàn)右端沒(méi)有出現(xiàn)s s,則s不可能為重的假幣；判斷比真幣輕判斷比真幣重課后思考題題一：題一：給一個(gè)很長(zhǎng)的數(shù)字串S：123456891011121314，它是由所有的自然數(shù)從小到大依次排列起來(lái)的。任意給一個(gè)數(shù)字串S1(其長(zhǎng)度不大于10)，求出S1在S中第一次出現(xiàn)的位置。比如：輸入101，輸出為10考慮： 2132課后思考題題二：題二：形如ax3+bx2+cx+d=0 的一個(gè)一元三次方程。