基本的算法策略PPT課件

1、第四章第四章 基本的算法策略基本的算法策略4.1 迭代算法迭代算法 概念概念 用變量的舊值遞推出新值的解決問題的方法用變量的舊值遞推出新值的解決問題的方法 適合的范圍適合的范圍 數(shù)值計(jì)算數(shù)值計(jì)算 類型類型（1 1）遞推法）遞推法 s sn n=s=sn-1n-1+A+An n（2 2）倒推法）倒推法411 遞推遞推法 【例【例1】兔子繁殖問題】兔子繁殖問題問題描述：?jiǎn)栴}描述：一對(duì)兔子從出生后第三個(gè)月開始，每月生一對(duì)兔子從出生后第三個(gè)月開始，每月生一對(duì)小兔子。小兔子到第三個(gè)月又開始生下一代小一對(duì)小兔子。小兔子到第三個(gè)月又開始生下一代小兔子。假若兔子只生不死，一月份抱來(lái)一對(duì)剛出生兔子。假若兔子只生

2、不死，一月份抱來(lái)一對(duì)剛出生的小兔子，問一年中每個(gè)月各有多少只兔子。的小兔子，問一年中每個(gè)月各有多少只兔子。問題分析：?jiǎn)栴}分析：則繁殖過程如下：則繁殖過程如下： 一月一月 二月二月 三月三月 四月四月 五月五月 六月六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 數(shù)學(xué)建模：數(shù)學(xué)建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，。算法算法1 1： main( )main( ) int i,a=1,b=1; int i,a=1,b=1; print(a,b); print(a,b); for(i=1;i for(i=1;i=10;i+)=10;i+) c=a+b; c=a

3、+b; print (c); print (c); a=b; a=b; b=c b=c； 4.1.2 4.1.2 倒推法倒推法 所謂所謂倒推法倒推法：是對(duì)某些特殊問題所采用的違反通常習(xí)慣的，從：是對(duì)某些特殊問題所采用的違反通常習(xí)慣的，從 后向前推解問題的方法。后向前推解問題的方法?！纠俊纠亢镒映蕴覇栴}猴子吃桃問題一只小猴子摘了若干桃子，每天吃現(xiàn)有桃的一半多一個(gè)，一只小猴子摘了若干桃子，每天吃現(xiàn)有桃的一半多一個(gè)，到第到第1010天時(shí)就只有一個(gè)桃子了，求原有多少個(gè)桃？天時(shí)就只有一個(gè)桃子了，求原有多少個(gè)桃？數(shù)學(xué)模型：數(shù)學(xué)模型：每天的桃子數(shù)為：每天的桃子數(shù)為：a a1010=1, a=1, a9

4、9= =（1+a1+a1010）* *2, a2, a8 8= =（1+a1+a9 9）* *2,a2,a1010=1=1， 遞推公式為：遞推公式為：a ai i= =（1+a1+ai+1i+1）* *2 I = 9,8,7,612 I = 9,8,7,61算法如下算法如下 ： main( )main( ) int i,s; int i,s; s=1; s=1; for (i=9 ;i=1;i=i-1) for (i=9 ;i=1;i=i-1) s=(s s=(s+1）*2 print (s) print (s)； 4.2 蠻力法蠻力法 蠻力法蠻力法是基于計(jì)算機(jī)運(yùn)算速度快這一特性，在解決問題時(shí)

5、采是基于計(jì)算機(jī)運(yùn)算速度快這一特性，在解決問題時(shí)采取的一種取的一種“ “懶惰懶惰” ”的策略。這種策略不經(jīng)過（或者說(shuō)是經(jīng)過很少的）的策略。這種策略不經(jīng)過（或者說(shuō)是經(jīng)過很少的）思考，把問題的所有情況或所有過程交給計(jì)算機(jī)去一一嘗試，從思考，把問題的所有情況或所有過程交給計(jì)算機(jī)去一一嘗試，從中找出問題的解。中找出問題的解。 應(yīng)用應(yīng)用 蠻力策略的應(yīng)用很廣，具體表現(xiàn)形式各異，數(shù)據(jù)結(jié)構(gòu)課程中學(xué)蠻力策略的應(yīng)用很廣，具體表現(xiàn)形式各異，數(shù)據(jù)結(jié)構(gòu)課程中學(xué)習(xí)的：選擇排序、冒泡排序、插入排序、順序查找、樸素的字符習(xí)的：選擇排序、冒泡排序、插入排序、順序查找、樸素的字符串匹配等，都是蠻力策略具體應(yīng)用。串匹配等，都是蠻力策

6、略具體應(yīng)用。4 42 21 1 枚舉法枚舉法 枚舉枚舉（ enumerate）法（窮舉法）是蠻力策略的一種表現(xiàn)形式，）法（窮舉法）是蠻力策略的一種表現(xiàn)形式，也是一種使用非常普遍的思維方法。它是根據(jù)問題中的條件將可能也是一種使用非常普遍的思維方法。它是根據(jù)問題中的條件將可能的情況一一列舉出來(lái)，逐一嘗試從中找出滿足問題條件的解。但有的情況一一列舉出來(lái)，逐一嘗試從中找出滿足問題條件的解。但有時(shí)一一列舉出的情況數(shù)目很大，如果超過了我們所能忍受的范圍，時(shí)一一列舉出的情況數(shù)目很大，如果超過了我們所能忍受的范圍，則需要進(jìn)一步考慮，排除一些明顯不合理的情況，盡可能減少問題則需要進(jìn)一步考慮，排除一些明顯不合理的

7、情況，盡可能減少問題可能解的列舉數(shù)目?？赡芙獾牧信e數(shù)目。用枚舉法解決問題，通?？梢詮膬蓚€(gè)方面進(jìn)行算法設(shè)計(jì)：用枚舉法解決問題，通?？梢詮膬蓚€(gè)方面進(jìn)行算法設(shè)計(jì)： 1）找出枚舉范圍：分析問題所涉及的各種情況。找出枚舉范圍：分析問題所涉及的各種情況。 2 2）找出約束條件：分析問題的解需要滿足的條件，并用邏輯）找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達(dá)式表示。表達(dá)式表示。【例】解數(shù)字迷：【例】解數(shù)字迷： A B C A BA B C A B A A D D D D D D D D D D D D算法設(shè)計(jì)算法設(shè)計(jì)1 1：按乘法枚舉按乘法枚舉1)1)枚舉范圍為：枚舉范圍為： A A：3939（

8、A=1A=1，2 2時(shí)積不會(huì)得到六位數(shù)）時(shí)積不會(huì)得到六位數(shù)）,B,B：09,09, C C：09 09 六位數(shù)表示為六位數(shù)表示為A A* *10000+B10000+B* *1000+C1000+C* *100+A100+A* *10+B10+B， 共嘗試共嘗試800800次。次。2)2)約束條件為：約束條件為： 每次嘗試，先求每次嘗試，先求5 5位數(shù)與位數(shù)與A A的積，再測(cè)試積的各位是否相的積，再測(cè)試積的各位是否相 同，若相同則找到了問題的解。同，若相同則找到了問題的解。 測(cè)試積的各位是否相同比較簡(jiǎn)單的方法是，從低位開始，測(cè)試積的各位是否相同比較簡(jiǎn)單的方法是，從低位開始， 每次都取數(shù)據(jù)的個(gè)位

9、，然后整除每次都取數(shù)據(jù)的個(gè)位，然后整除1010，使高位的數(shù)字不斷變，使高位的數(shù)字不斷變 成個(gè)位，并逐一比較。成個(gè)位，并逐一比較。 算法算法1 1如下：如下：main（ ） int A,B,C,D,E,E1,F,G1,G2,i; for(A=3; A=9; A+) for(B=0; B=9; B+) for(C=0; C=9; C+) F=A*10000+B*1000+C*100+A*10+B; E=F*A； E1=E; G1=E1 mod 10; for(i=1; i=5; i+) G2=G1; E1=E1/10; G1= E1 mod 10; if(G1G2 ) break; if(i=6)

10、 print( F，”*”，A，”=”，E); 4.3 分而治之算法分而治之算法431 分治算法框架分治算法框架 1算法設(shè)計(jì)思想算法設(shè)計(jì)思想分治法求解問題的過程是，將整個(gè)問題分解成若干個(gè)小問題后分分治法求解問題的過程是，將整個(gè)問題分解成若干個(gè)小問題后分而治之。如果分解得到的子問題相對(duì)來(lái)說(shuō)還太大，則可反復(fù)使用而治之。如果分解得到的子問題相對(duì)來(lái)說(shuō)還太大，則可反復(fù)使用分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出方分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出方便求解的子問題，必要時(shí)逐步合并這些子問題的解，從而得到問便求解的子問題，必要時(shí)逐步合并這些子問題的解，從而得到問題的解。題的

11、解。分治法的基本步驟在每一層遞歸上都有三個(gè)步驟：分治法的基本步驟在每一層遞歸上都有三個(gè)步驟： 1）分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原）分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題；問題形式相同的子問題； 2）解決：若子問題規(guī)模較小而容易被解決則直接解，否則再）解決：若子問題規(guī)模較小而容易被解決則直接解，否則再繼續(xù)分解為更小的子問題，直到容易解決；繼續(xù)分解為更小的子問題，直到容易解決； 3）合并：將已求解的各個(gè)子問題的解，逐步合并為原問題的）合并：將已求解的各個(gè)子問題的解，逐步合并為原問題的解。解。說(shuō)明：說(shuō)明： 有時(shí)問題分解后，不必求解所有的子問題，也就

12、不必作第三有時(shí)問題分解后，不必求解所有的子問題，也就不必作第三步的操作。比如折半查找，在判別出問題的解在某一個(gè)子問題步的操作。比如折半查找，在判別出問題的解在某一個(gè)子問題中后，其它的子問題就不必求解了，問題的解就是最后（最?。┲泻螅渌淖訂栴}就不必求解了，問題的解就是最后（最?。┑淖訂栴}的解。分治法的這類應(yīng)用，又稱為的子問題的解。分治法的這類應(yīng)用，又稱為“減治法減治法”。 多數(shù)問題需要所有子問題的解，并由子問題的解，使用恰多數(shù)問題需要所有子問題的解，并由子問題的解，使用恰當(dāng)?shù)姆椒ê喜⒊蔀檎麄€(gè)問題的解，比如合并排序，就是不斷將當(dāng)?shù)姆椒ê喜⒊蔀檎麄€(gè)問題的解，比如合并排序，就是不斷將子問題中已排好

13、序的解合并成較大規(guī)模的有序子集。子問題中已排好序的解合并成較大規(guī)模的有序子集。 2適合用分治法策略的問題適合用分治法策略的問題當(dāng)求解一個(gè)輸入規(guī)模為當(dāng)求解一個(gè)輸入規(guī)模為n且取值又相當(dāng)大的問題時(shí)，用蠻力策略且取值又相當(dāng)大的問題時(shí)，用蠻力策略效率一般得不到保證。若問題能滿足以下幾個(gè)條件，就能用分治法效率一般得不到保證。若問題能滿足以下幾個(gè)條件，就能用分治法來(lái)提高解決問題的效率。來(lái)提高解決問題的效率。1） 能將這能將這n個(gè)數(shù)據(jù)分解成個(gè)數(shù)據(jù)分解成k個(gè)不同子集合，且得到個(gè)不同子集合，且得到k個(gè)子集合是個(gè)子集合是可以獨(dú)立求解的子問題，其中可以獨(dú)立求解的子問題，其中1kn；2） 分解所得到的子問題與原問題具有

14、相似的結(jié)構(gòu)，便于利用遞分解所得到的子問題與原問題具有相似的結(jié)構(gòu)，便于利用遞歸或循環(huán)機(jī)制；歸或循環(huán)機(jī)制；在求出這些子問題的解之后，就可以推解出原問題的解；在求出這些子問題的解之后，就可以推解出原問題的解； 432 二分法二分法 不同于現(xiàn)實(shí)中對(duì)問題（或工作）的分解，可能會(huì)考慮問題不同于現(xiàn)實(shí)中對(duì)問題（或工作）的分解，可能會(huì)考慮問題（或工作）的重點(diǎn)、難點(diǎn)、承擔(dān)人員的能力等來(lái)進(jìn)行問題的分（或工作）的重點(diǎn)、難點(diǎn)、承擔(dān)人員的能力等來(lái)進(jìn)行問題的分解和分配。在算法設(shè)計(jì)中每次一個(gè)問題分解成的子問題個(gè)數(shù)一解和分配。在算法設(shè)計(jì)中每次一個(gè)問題分解成的子問題個(gè)數(shù)一般是固定的，每個(gè)子問題的規(guī)模也是平均分配的。當(dāng)每次都將般是

15、固定的，每個(gè)子問題的規(guī)模也是平均分配的。當(dāng)每次都將問題分解為原問題規(guī)模的一半時(shí)，稱為二分法。二分法是分治問題分解為原問題規(guī)模的一半時(shí)，稱為二分法。二分法是分治法較常用的分解策略，數(shù)據(jù)結(jié)構(gòu)課程中的折半查找、歸并排序法較常用的分解策略，數(shù)據(jù)結(jié)構(gòu)課程中的折半查找、歸并排序等算法都是采用此策略實(shí)現(xiàn)的。等算法都是采用此策略實(shí)現(xiàn)的。分治法的一般的算法設(shè)計(jì)模式如下：分治法的一般的算法設(shè)計(jì)模式如下：Divide-and-Conquer(int n) /nDivide-and-Conquer(int n) /n為問題規(guī)模為問題規(guī)模/ / if if （nn0nn0） /n0 /n0 為可解子問題的規(guī)模為可解子問

16、題的規(guī)模/ / 解子問題；解子問題； return(return(子問題的解子問題的解) )； for for （i=1 ;i=k;i+i=1 ;i=k;i+） / /分解為較小子問題分解為較小子問題p1,p2,pk/p1,p2,pk/ yi=Divide-and-Conquer(|Pi|); / yi=Divide-and-Conquer(|Pi|); /遞歸解決遞歸解決Pi/Pi/ T =MERGE(y1,y2,.,yk); / T =MERGE(y1,y2,.,yk); /合并子問題合并子問題/ / return(T); return(T); 【例【例1 1】金塊問題：】金塊問題： 老板

17、有一袋金塊老板有一袋金塊( (共共n n塊塊) )，最優(yōu)秀，最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的一塊。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。的比較次數(shù)找出最重的金塊。 算法設(shè)計(jì)算法設(shè)計(jì)1：比較簡(jiǎn)單的方法是逐個(gè)的進(jìn)行比較查找。先拿比較簡(jiǎn)單的方法是逐個(gè)的進(jìn)行比較查找。先拿兩塊比較重量，留下重的一個(gè)與下一塊比較，兩塊比較重量，留下重的一個(gè)與下一塊比較，直到全部比較完畢，就找到了最重的金子。算直到全部比較完畢，就找到了最重的金子。算法類似于一趟選擇排序，法類似

18、于一趟選擇排序， 算法如下：算法如下：maxmin( float a,int n) max=min=a1; for(i=2; i=n ;i+ ) if(max ai) min=ai; float an;float an;maxmin （int i, int j ,float &fmax, float &fminint i, int j ,float &fmax, float &fmin）int mid; float lmax, lmin, rmax, rmin;int mid; float lmax, lmin, rmax, rmin;if (i=j) fmax

19、= ai; fmin=ai;if (i=j) fmax= ai; fmin=ai;else if (i=j-1)else if (i=j-1) if(aiaj) fmax=ajif(airmax) fmax=lmax;if(lmaxrmax) fmax=lmax;else fmax=rmax;else fmax=rmax;if(lminrmin) fmin=rmin;if(lminrmin) fmin=rmin;else fmin=lmin;else fmin=lmin; 【例】【例】大整數(shù)乘法大整數(shù)乘法在某些情況下，我們需要處理很大的整數(shù)，它在某些情況下，我們需要處理很大的整數(shù)，它無(wú)法在計(jì)算

20、機(jī)硬件能直接允許的范圍內(nèi)進(jìn)行表無(wú)法在計(jì)算機(jī)硬件能直接允許的范圍內(nèi)進(jìn)行表示和處理。若用浮點(diǎn)數(shù)來(lái)存儲(chǔ)它，只能近似地示和處理。若用浮點(diǎn)數(shù)來(lái)存儲(chǔ)它，只能近似地參與計(jì)算，計(jì)算結(jié)果的有效數(shù)字會(huì)受到限制。參與計(jì)算，計(jì)算結(jié)果的有效數(shù)字會(huì)受到限制。若要精確地表示大整數(shù)，并在計(jì)算結(jié)果中要求若要精確地表示大整數(shù)，并在計(jì)算結(jié)果中要求精確地得到所有位數(shù)上的數(shù)字，就必須用軟件精確地得到所有位數(shù)上的數(shù)字，就必須用軟件的方法來(lái)實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算。請(qǐng)?jiān)O(shè)計(jì)一個(gè)的方法來(lái)實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算。請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法位大整數(shù)的乘法運(yùn)算。運(yùn)算。算法設(shè)計(jì)：算法設(shè)計(jì)：設(shè)設(shè)X和和Y都是都是

21、n位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積X*Y。圖圖4-10 4-10 大整數(shù)大整數(shù)X X和和Y Y的分段的分段按照乘法分配律，分解后的計(jì)算過程如下：按照乘法分配律，分解后的計(jì)算過程如下：記：記：X=AX=A* *2 2n/2n/2+B +B ，Y=CY=C* *2 2n/2n/2+D+D。這樣，。這樣，X X和和Y Y的乘積為：的乘積為：X*Y=(A*2n/2+B)(C*2n/2+D)=A*C*2n+(AD+CB)*2n/2+B*D (1)(1) T T（1 1）=1=1 T T（n n）=4T(n/2) =4T(n/2) （2 2） 由此遞歸式迭代過程如下：由此遞歸式迭代過程如下：T(n)