1、第四章 根本的算法戰略4.1 迭代算法概念 用變量的舊值遞推出新值的處理問題的方法適宜的范圍 數值計算類型1遞推法 sn=sn-1+An2倒推法411 遞推法 【例1】兔子繁衍問題問題描畫：一對兔子從出生后第三個月開場，每月生一對小兔子。小兔子到第三個月又開場生下一代小兔子。假假設兔子只生不死，一月份抱來一對剛出生的小兔子，問一年中每個月各有多少只兔子。問題分析：那么繁衍過程如下： 一月 二月 三月 四月 五月 六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 數學建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，。算法1： main( ) int i,a=1,b=1

2、; print(a,b); for(i=1;i=10;i+) c=a+b; print (c); a=b; b=c； 4.1.2 倒推法 所謂倒推法：是對某些特殊問題所采用的違反通常習慣的，從 后向前推解問題的方法。【例】猴子吃桃問題一只小猴子摘了假設干桃子，每天吃現有桃的一半多一個，到第10天時就只需一個桃子了，求原有多少個桃？數學模型：每天的桃子數為：a10=1, a9=1+a10*2, a8=1+a9*2,a10=1， 遞推公式為：ai=1+ai+1*2 I = 9,8,7,61算法如下 ： main( ) int i,s; s=1; for (i=9 ;i=1;i=i-1) s=(s+

3、1*2 print (s)； 4.2 蠻力法 蠻力法是基于計算機運算速度快這一特性，在處理問題時采取的一種“懶惰的戰略。這種戰略不經過或者說是經過很少的思索，把問題的一切情況或一切過程交給計算機去一一嘗試，從中找出問題的解。 運用 蠻力戰略的運用很廣，詳細表現方式各異，數據構造課程中學習的：選擇排序、冒泡排序、插入排序、順序查找、樸素的字符串匹配等，都是蠻力戰略詳細運用。421 枚舉法 枚舉 enumerate法窮舉法是蠻力戰略的一種表現方式，也是一種運用非常普遍的思想方法。它是根據問題中的條件將能夠的情況一一列舉出來，逐一嘗試從中找出滿足問題條件的解。但有時一一列舉出的情況數目很大，假設超越

4、了我們所能忍受的范圍，那么需求進一步思索，排除一些明顯不合理的情況，盡能夠減少問題能夠解的列舉數目。用枚舉法處理問題，通常可以從兩個方面進展算法設計： 1找出枚舉范圍：分析問題所涉及的各種情況。 2找出約束條件：分析問題的解需求滿足的條件，并用邏輯表達式表示。【例】解數字迷： A B C A B A D D D D D D算法設計1：按乘法枚舉1)枚舉范圍為： A：39A=1，2時積不會得到六位數,B：09, C：09 六位數表示為A*10000+B*1000+C*100+A*10+B， 共嘗試800次。2)約束條件為： 每次嘗試，先求5位數與A的積，再測試積的各位能否相 同，假設一樣那么找到

5、了問題的解。 測試積的各位能否一樣比較簡單的方法是，從低位開場， 每次都取數據的個位，然后整除10，使高位的數字不斷變 成個位，并逐一比較。 算法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) pri

6、nt( F，*，A，=，E); 4.3 分而治之算法431 分治算法框架 1算法設計思想分治法求解問題的過程是，將整個問題分解成假設干個小問題后分而治之。假設分解得到的子問題相對來說還太大，那么可反復運用分治戰略將這些子問題分成更小的同類型子問題，直至產生出方便求解的子問題，必要時逐漸合并這些子問題的解，從而得到問題的解。分治法的根本步驟在每一層遞歸上都有三個步驟： 1分解：將原問題分解為假設干個規模較小，相互獨立，與原問題方式一樣的子問題； 2處理：假設子問題規模較小而容易被處理那么直接解，否那么再繼續分解為更小的子問題，直到容易處理； 3合并：將已求解的各個子問題的解，逐漸合并為原問題的解

7、。闡明： 有時問題分解后，不用求解一切的子問題，也就不用作第三步的操作。比如折半查找，在判別出問題的解在某一個子問題中后，其它的子問題就不用求解了，問題的解就是最后最小的子問題的解。分治法的這類運用，又稱為“減治法。 多數問題需求一切子問題的解，并由子問題的解，運用恰當的方法合并成為整個問題的解，比如合并排序，就是不斷將子問題中已排好序的解合并成較大規模的有序子集。 2適宜用分治法戰略的問題當求解一個輸入規模為n且取值又相當大的問題時，用蠻力戰略效率普通得不到保證。假設問題能滿足以下幾個條件，就能用分治法來提高處理問題的效率。1 能將這n個數據分解成k個不同子集合，且得到k個子集合是可以獨立求

8、解的子問題，其中1kn；2 分解所得到的子問題與原問題具有類似的構造，便于利用遞歸或循環機制；在求出這些子問題的解之后，就可以推解出原問題的解； 432 二分法 不同于現實中對問題或任務的分解，能夠會思索問題或任務的重點、難點、承當人員的才干等來進展問題的分解和分配。在算法設計中每次一個問題分解成的子問題個數普通是固定的，每個子問題的規模也是平均分配的。當每次都將問題分解為原問題規模的一半時，稱為二分法。二分法是分治法較常用的分解戰略，數據構造課程中的折半查找、歸并排序等算法都是采用此戰略實現的。分治法的普通的算法設計方式如下：Divide-and-Conquer(int n) /n為問題規模

9、/ if nn0 /n0 為可解子問題的規模/ 解子問題； return(子問題的解)；for i=1 ;i=k;i+ /分解為較小子問題p1,p2,pk/ yi=Divide-and-Conquer(|Pi|); /遞歸處理Pi/ T =MERGE(y1,y2,.,yk); /合并子問題/ return(T); 【例1】金塊問題： 老板有一袋金塊(共n塊)，最優秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設有一臺比較分量的儀器，我們希望用最少的比較次數找出最重的金塊。算法設計1：比較簡單的方法是逐個的進展比較查找。先拿兩塊比較分量，留下重的一個與下一塊比較，直到全部比較終了，

10、就找到了最重的金子。算法類似于一趟選擇排序， 算法如下：maxmin( float a,int n) max=min=a1; for(i=2; i=n ;i+ ) if(max ai) min=ai; 算法分析1：算法中需求n-1次比較得到max。最好的情況是金塊是由小到大取出的，不需求進展與min的比較，共進展n-1次比較。最壞的情況是金塊是由大到小取出的，需求再經過n-1次比較得到min算法設計2:在含nn是2的冪n=2個元素的集合中尋覓極大元和極小元。用分治法二分法：1 將數據等分為兩組兩組數據能夠差1，2遞歸分解直到每組元素的個數2，可簡單地找到最大小值。3回溯時將分解的兩組解大者取大

11、，小者取小，合并為當前問題的解。算法2 遞歸求取最大和最小元素 float an;maxmin int i, int j ,float &fmax, float &fminint mid; float lmax, lmin, rmax, rmin;if (i=j) fmax= ai; fmin=ai;else if (i=j-1) if(airmax) fmax=lmax;else fmax=rmax;if(lminrmin) fmin=rmin;else fmin=lmin; 【例】大整數乘法在某些情況下，我們需求處置很大的整數，它無法在計算機硬件能直接允許的范圍內進展表示和處置。假設用浮點

12、數來存儲它，只能近似地參與計算，計算結果的有效數字會遭到限制。假設要準確地表示大整數，并在計算結果中要求準確地得到一切位數上的數字，就必需用軟件的方法來實現大整數的算術運算。請設計一個有效的算法，可以進展兩個n位大整數的乘法運算。算法設計：設X和Y都是n位的二進制整數，如今要計算它們的乘積X*Y。圖4-10 大整數X和Y的分段按照乘法分配律，分解后的計算過程如下：記：X=A*2n/2+B ，Y=C*2n/2+D。這樣，X和Y的乘積為：X*Y=(A*2n/2+B)(C*2n/2+D)=A*C*2n+(AD+CB)*2n/2+B*D(1) T1=1 Tn=4T(n/2) 2 由此遞歸式迭代過程如下

13、：T(n)=4T(n/2) =4(4T(n/4)T(n/4) =16*T(n/8) = =O4k= O(nlog4) =On2所以可得算法的時間復雜度為T(n)=O(n2)。模型改良：可以把X*Y寫成另一種方式：X*Y=A*C*2n+(A-B)(D-C)+AC+BD*2n/2+B*D (3)式(3)看起來比式(1)復雜，但它僅需做3次n/2位整數的乘法：AC，BD和(A-B)(D-C)，6次加、減法和2次移位。由此可得: (4)用解遞歸方程的迭代公式法，無妨設n=2k： T(n)=3T(n/2) =3(3T(n/4) =9(T(n/8) = =3k +3k-1 *2c+3k-2 *4c+3c2k-1+c2k = O(nlog3)那么得到T(n)=O(nlog3)=O(n1.59)。434 其它分治方法 【例】選擇問題： 對于給定的n 個元素的數組a0:n-1，要求從中找出第k小的元