算法詳解及練習題

1、1算法詳解及練習題算法詳解及練習題目錄第一講第一講窮舉法窮舉法1第二講第二講字符與字符串處理字符與字符串處理1616第三講第三講不同進制轉(zhuǎn)換不同進制轉(zhuǎn)換2525第四講第四講高精度計算高精度計算2626第五講第五講數(shù)據(jù)排序數(shù)據(jù)排序3030第六講第六講約瑟夫問題（紙牌問題）約瑟夫問題（紙牌問題）3434第七講第七講矩陣（遞推問題）矩陣（遞推問題）4040第八講第八講排列組合排列組合4343第九講第九講貪心算法貪心算法4747第十講第十講遞歸

2、算法遞歸算法5656第一講第一講窮舉法窮舉法一、窮舉法的基本概念窮舉方法是基于計算機特點而進行解題的思維方法。一般是在一時找不出解決問題的更好途徑（即從數(shù)學上找不到求解的公式或規(guī)則）時，可以根據(jù)問題中的的部分條件（約束條件）將所有可能解的情況列舉出來，然后通過一一驗證是否符合整個問題的求解要求，而得到問題的解。這樣解決問題的方法我們稱之為窮舉算法。窮舉算法特點是算法簡單，但運行時所花費的時間量大。有些問題所列舉出來的情況數(shù)目會大得驚人，

3、就是用高速的電子計算機運行，其等待運行結(jié)果的時間也將使人無法忍受。因此，我們在用窮舉方法解決問題時，應盡可能將明顯的不符合條件的情況排除在外，以盡快取得問題的解。二、算法模式問題解的可能搜索的范圍：用循環(huán)或循環(huán)嵌套結(jié)構實現(xiàn)，寫出符合問題解的條件。能使程序優(yōu)化的語句，以便縮小搜索范圍，減少程序運行時間。三、使用窮舉法設計算法例1：百錢買百雞問題：有一個人有一百塊錢，打算買一百只雞。到市場一看，大雞三塊錢一只，小雞一塊錢三只，不大不小的雞兩

4、塊錢一只?，F(xiàn)在，請你編一程序，幫他計劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？算法分析：此題很顯然是用枚舉法，我們以三種雞的個數(shù)為枚舉對象（分別設為xyz）以三種雞的總數(shù)（xyz）和買雞用去的錢的總數(shù)(x3y2z)為判定條件，窮舉各種雞的個數(shù)。下面是解這個百雞問題的程序varxyz:integer3tx:integersst:stringc:beginfx:=123to329do枚舉所有可能的解begint:=0str(xst)

5、把整數(shù)x轉(zhuǎn)化為字符串，存放在st中str(x2s)st:=stsstr(x3s)st:=stsfc:=1to9do枚舉9個字符，判斷是否都在st中ifpos(cst)0theninc(t)elsebreak如果不在st中，則退出循環(huán)ift=9thenwriteln(xx2x3)endend.在枚舉法解題中，判定條件的確定也是很重要的，如果約束條件不對或者不全面，就窮舉不出正確的結(jié)果，我們再看看下面的例子。例3：古希臘人認為因子的和等于它

6、本身的數(shù)是一個完全數(shù)（自身因子除外），例如28的因子是1、2、4、7、14，且124714=28，則28是一個完全數(shù)，編寫一個程序求2～1000內(nèi)的所有完全數(shù)。分析：本題是一個搜索問題，搜索范圍2～1000，找出該范圍內(nèi)的完全數(shù)；完全數(shù)必須滿足的條件：因子的和等于該數(shù)據(jù)的本身。問題關鍵在于將該數(shù)的因子一一尋找出來，并求出因子的和。程序如下：Programp3_1Varabs:integerBeginFa:=2to1000doBegins