基本的算法策略PPT課件

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

2、不死，一月份抱來一對剛出生的小兔子，問一年中每個月各有多少只兔子。的小兔子，問一年中每個月各有多少只兔子。問題分析：問題分析：則繁殖過程如下：則繁殖過程如下： 一月一月 二月二月 三月三月 四月四月 五月五月 六月六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 數(shù)學建模：數(shù)學建模：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 倒推法倒推法 所謂所謂倒推法倒推法：是對某些特殊問題所采用的違反通常習慣的，從：是對某些特殊問題所采用的違反通常習慣的，從 后向前推解問題的方法。后向前推解問題的方法?！纠俊纠亢镒映蕴覇栴}猴子吃桃問題一只小猴子摘了若干桃子，每天吃現(xiàn)有桃的一半多一個，一只小猴子摘了若干桃子，每天吃現(xiàn)有桃的一半多一個，到第到第1010天時就只有一個桃子了，求原有多少個桃？天時就只有一個桃子了，求原有多少個桃？數(shù)學模型：數(shù)學模型：每天的桃子數(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 蠻力法蠻力法 蠻力法蠻力法是基于計算機運算速度快這一特性，在解決問題時

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

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

7、情況，盡可能減少問題可能解的列舉數(shù)目?？赡芙獾牧信e數(shù)目。用枚舉法解決問題，通常可以從兩個方面進行算法設(shè)計：用枚舉法解決問題，通?？梢詮膬蓚€方面進行算法設(shè)計： 1）找出枚舉范圍：分析問題所涉及的各種情況。找出枚舉范圍：分析問題所涉及的各種情況。 2 2）找出約束條件：分析問題的解需要滿足的條件，并用邏輯）找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達式表示。表達式表示。【例】解數(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è)計算法設(shè)計1 1：按乘法枚舉按乘法枚舉1)1)枚舉范圍為：枚舉范圍為： A A：3939（

8、A=1A=1，2 2時積不會得到六位數(shù)）時積不會得到六位數(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的積，再測試積的各位是否相的積，再測試積的各位是否相 同，若相同則找到了問題的解。同，若相同則找到了問題的解。 測試積的各位是否相同比較簡單的方法是，從低位開始，測試積的各位是否相同比較簡單的方法是，從低位開始， 每次都取數(shù)據(jù)的個位

9、，然后整除每次都取數(shù)據(jù)的個位，然后整除1010，使高位的數(shù)字不斷變，使高位的數(shù)字不斷變 成個位，并逐一比較。成個位，并逐一比較。 算法算法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è)計思想算法設(shè)計思想分治法求解問題的過程是，將整個問題分解成若干個小問題后分分治法求解問題的過程是，將整個問題分解成若干個小問題后分而治之。如果分解得到的子問題相對來說還太大，則可反復使用而治之。如果分解得到的子問題相對來說還太大，則可反復使用分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出方分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出方便求解的子問題，必要時逐步合并這些子問題的解，從而得到問便求解的子問題，必要時逐步合并這些子問題的解，從而得到問題的解。題的

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

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

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

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

15、固定的，每個子問題的規(guī)模也是平均分配的。當每次都將問題分解為原問題規(guī)模的一半時，稱為二分法。二分法是分治問題分解為原問題規(guī)模的一半時，稱為二分法。二分法是分治法較常用的分解策略，數(shù)據(jù)結(jié)構(gòu)課程中的折半查找、歸并排序法較常用的分解策略，數(shù)據(jù)結(jié)構(gòu)課程中的折半查找、歸并排序等算法都是采用此策略實現(xiàn)的。等算法都是采用此策略實現(xiàn)的。分治法的一般的算法設(shè)計模式如下：分治法的一般的算法設(shè)計模式如下：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è)有一臺比較重量的儀器，我們希望用最少的一塊。假設(shè)有一臺比較重量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。的比較次數(shù)找出最重的金塊。 算法設(shè)計算法設(shè)計1：比較簡單的方法是逐個的進行比較查找。先拿比較簡單的方法是逐個的進行比較查找。先拿兩塊比較重量，留下重的一個與下一塊比較，兩塊比較重量，留下重的一個與下一塊比較，直到全部比較完畢，就找到了最重的金子。算直到全部比較完畢，就找到了最重的金子。算法類似于一趟選擇排序，法類似

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ù)，它無法在計算

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

21、n位的二進制整數(shù)，現(xiàn)在要計算它們的乘積位的二進制整數(shù)，現(xiàn)在要計算它們的乘積X*Y。圖圖4-10 4-10 大整數(shù)大整數(shù)X X和和Y Y的分段的分段按照乘法分配律，分解后的計算過程如下：按照乘法分配律，分解后的計算過程如下：記：記：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)