算法詳解及練習(xí)題

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

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

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

4、塊錢一只?，F(xiàn)在，請你編一程序，幫他計劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？算法分析：此題很顯然是用枚舉法，我們以三種雞的個數(shù)為枚舉對象（分別設(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：古希臘人認(rèn)為因子的和等于它

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ù)的本身。問題關(guān)鍵在于將該數(shù)的因子一一尋找出來，并求出因子的和。程序如下：Programp3_1Varabs:integerBeginFa:=2to1000doBegins