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

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

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

3、要重復(fù) 枚舉算法基本思想 o 枚舉算法枚舉算法 也稱之為窮舉算法，就是按照問題本身的性質(zhì)，一一一一 列舉出該問題所有可能的解列舉出該問題所有可能的解，并在列舉的過程中，逐一逐一 檢驗每個可能解是否是問題的真正解檢驗每個可能解是否是問題的真正解。若是，則采納這 個解；否則拋棄它。 解的高準確性和全面性解的高準確性和全面性 實現(xiàn)簡單，枚舉算法通過循環(huán)來逐一列舉和驗證可能解實現(xiàn)簡單，枚舉算法通過循環(huán)來逐一列舉和驗證可能解 效率提升空間比較大效率提升空間比較大 枚舉三步 1. 確定枚舉對象確定枚舉對象 枚舉對象也可以理解為是問題解的 表達形式，一般需要用若干參數(shù)來描述一般需要用若干參數(shù)來描述 o參數(shù)之

4、間需要相互獨立，而且，參數(shù)數(shù)目越少，問題解 的搜索空間的維度也相應(yīng)地?。?o每個參數(shù)的取值范圍越小，問題解的搜索空間也越小。 2. 逐一列舉可能解逐一列舉可能解 根據(jù)枚舉對象的參數(shù)構(gòu)造循環(huán)構(gòu)造循環(huán)， 一一列舉其表達式的每一種取值情況。 3. 逐一驗證可能解逐一驗證可能解 根據(jù)問題解的要求，一一驗證一一驗證枚 舉對象表達式的每一個取值，如果滿足條件，則采 納它，否則，拋棄之。 模糊數(shù)字 任務(wù)描述任務(wù)描述：一張單據(jù)上有一個5位數(shù)的編碼，因為保管不善，其 百位數(shù)已經(jīng)變得模糊不請。但是知道這個5位數(shù)是57和67的 倍數(shù)?，F(xiàn)在要設(shè)計一個算法，輸出所有滿足這些條件的5位 數(shù)，并統(tǒng)計這樣的數(shù)的個數(shù)。 輸入：

5、輸入：每一行對應(yīng)一個測試樣例，每一行包含4個數(shù)字，依次是 萬位數(shù)，千位數(shù)，十位數(shù)和個位數(shù)。最后一行包含4個-1， 表示輸入結(jié)束。 輸出：輸出：每組測試樣例的結(jié)果輸出占一行，第一個數(shù)字表示滿足條 件的編碼個數(shù)，后面按升序輸出所有滿足條件的編碼，數(shù)字 與數(shù)字之間用空格隔開。 19？95 模糊數(shù)字 o 枚舉對象 Obj(h) ：記h百位數(shù)數(shù)字， h =09 o 逐一列舉 for(h=0;h10;h+) o 逐一驗證 19h95能否整除57和67 模糊數(shù)字續(xù) o 任務(wù)描述：任務(wù)描述：一張單據(jù)上有一個5位數(shù)的編碼，因為保管不善， 其萬位數(shù)字和百位數(shù)已經(jīng)變得模糊不請。但是知道這個5位 數(shù)是57和67的倍數(shù)

6、?，F(xiàn)在要設(shè)計一個算法，輸出所有滿足 這些條件的5位數(shù)，并統(tǒng)計這樣的數(shù)的個數(shù)。 o 輸入：輸入：每一行對應(yīng)一個測試樣例，每一行包含3個數(shù)字，依 次是千位數(shù)，十位數(shù)和個位數(shù)。最后一行包含3個-1，表示 輸入結(jié)束。 o 輸出：輸出：每組測試樣例的結(jié)果輸出占一行，第一個數(shù)字表示滿 足條件的編碼個數(shù)，后面按升序輸出所有滿足條件的編碼， 數(shù)字與數(shù)字之間用空格隔開。 ？9？95 模糊數(shù)字續(xù) o 枚舉對象obj(d1,d2) 萬位數(shù)數(shù)字，記為d1，d1=19 百位數(shù)數(shù)字，記為d2， d2 =09 o 逐一列舉 for(d1=1;d110;d1+) for(d2=0;d210;d2+) o 逐一驗證 d1 9

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

8、我國古代數(shù)學(xué)家張丘建在算經(jīng)中出了一 道題“雞翁一，值錢五；雞母一，值錢三；雞雛三，值 錢一。百錢買百雞，問雞翁、雞母、雞雛各幾何？”， 現(xiàn)在假定各雞種的價格不變，擁有的錢數(shù)為m，需要購 買的雞數(shù)為n，試求出所有可能的購買方案總數(shù)。 o 輸入輸入：每行對應(yīng)一個測試樣例，每一行包含2個數(shù)字， 分別為n 和m 。最后一行包含2個-1，表示輸入結(jié)束。 o 輸出輸出：每組測試樣例的結(jié)果輸出占一行，輸出可能購買 方案總數(shù)。 m錢n雞 o 枚舉對象 obj(n1， n2， n3) 雞翁數(shù)，記為n1， n1= 0n 雞母數(shù)，記為n2， n2 = 0n 雞雛數(shù)，記為n3， n3 = 0n o 逐一列舉 三層fo

9、r循環(huán)嵌套 o 逐一驗證 n1+ n2+ n3=n, 5n1+ 3n2+ n3 /3 =m m錢n雞-改進 o 枚舉對象 obj(n1， n2) 雞翁數(shù)，記為n1， n1= 0m/5 雞母數(shù)，記為n2， n2 = 0m/3 雞雛數(shù)，記為n3， n3 = n- n1 - n2 o 逐一列舉 二層for循環(huán)嵌套 o 逐一驗證 5n1+ 3n2+ n3 /3=m 算法復(fù)雜度O(m2) 真假銀幣 o任務(wù)描述：任務(wù)描述：張三有12枚銀幣，其中有11枚真幣和1枚假幣。假幣 看起來和真幣完全一樣，但是他們的重量不一樣。很遺憾的是， 張三不知道假幣比真幣輕還是重。但是他辦公室有一架天平，還 有一個聰明的助手。

10、經(jīng)過精心安排每次的稱重，助手保證在稱3次 后確定發(fā)現(xiàn)假幣。助手想跟張三開一個小小的玩笑，只告訴他每 次稱重的方案和天平的狀態(tài)，但是不告訴他哪個是假幣，假幣比 真幣輕還是重。請設(shè)計一個算法幫張三辨別真假銀幣。 o輸入：輸入：第一行包含一個正整數(shù)，表示測試數(shù)據(jù)的組數(shù)。每組測試 數(shù)據(jù)有三行，每行表示一次稱重的結(jié)果。張三和助手事先把銀幣 標號為AL。每次稱重的結(jié)果用3個以空格隔開的字符串表示：天 平左邊放置的銀幣標號，天平右邊放置的銀幣標號，以及平衡狀 態(tài)。其中平衡狀態(tài)用“up”、“down”和“even”表示，分別表示 右端高、右端低和平衡。另外，每次稱重天平左右的銀幣數(shù)總是 相等的。 o輸出：輸出

11、：每組測試數(shù)據(jù)的輸出占一行，輸出假銀幣的標號，并指明 它比真幣輕還是重，請則輸出 light，重則輸出 heavy。 真假銀幣 o 輸入樣例：輸入樣例： 1 ABCD EFGH even ABCI EFJK up ABIJ EFGH even o 輸出樣例：輸出樣例： K light 真假銀幣 o 枚舉對象 obj(c, s) c 為銀幣標號， c = AL s 為銀幣性質(zhì)， s = 輕，重，真 o 逐一列舉 o 逐一驗證 “Even”狀態(tài),天平任意一端出現(xiàn)s,則s不可 能為輕的假幣； “Up”狀態(tài),天平右端沒有出現(xiàn)右端沒有出現(xiàn)s s,則s不可能 為輕的假幣； “Down”狀態(tài),天平左端沒有出

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