1、第四章 基本的算法策略4.1 迭代算法4.2 蠻力算法4.3 分而治之算法4.4 貪婪算法4.5 動(dòng)態(tài)規(guī)劃 4.6 算法策略間的比較8/9/2022 4:03 PM14.1 迭代算法4.1.1 遞推法4.1.2 倒推法4.1.3 迭代法解方程8/9/2022 4:03 PM24.1.1 遞推法 【例1】兔子繁殖問(wèn)題問(wèn)題描述：一對(duì)兔子從出生后第三個(gè)月開(kāi)始，每月生一對(duì)小兔子。小兔子到第三個(gè)月又開(kāi)始生下一代小兔子。假若兔子只生不死，一月份抱來(lái)一對(duì)剛出生的小兔子，問(wèn)一年中每個(gè)月各有多少只兔子。問(wèn)題分析：因一對(duì)兔子從出生后第三個(gè)月開(kāi)始每月生一對(duì)小兔子，則每月新下小兔子的對(duì)兒數(shù)(用斜體數(shù)字表示)顯然由前兩

2、個(gè)月的小兔子的對(duì)兒數(shù)決定。則繁殖過(guò)程如下： 一月 二月 三月 四月 五月 六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 8/9/2022 4:03 PM38/9/2022 4:03 PM4算法1： main( ) int i,a=1,b=1; print(a,b); for(i=1;i=10;i+) c=a+b; print (c); a=b; b=c； 數(shù)學(xué)建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，。8/9/2022 4:03 PM5算法2：表4-1 遞推迭代表達(dá)式1 2 3 4 5 6 7 8 9a b c=a+b a=b+c b=a+c c=a+b

3、a=b+c b=a+c 由此歸納出可以用“c=a+b; a=b+c; b=c+a;”做循環(huán)“不變式”。算法2如下： main( ) int i,a=1,b=1; print(a,b); for(i=1; i=4;i+) c=a+b; a=b+c; b=c+a; print(a,b,c); 算法2，最后輸出的并不是12項(xiàng)，而是2+3*4共14項(xiàng)。 8/9/2022 4:03 PM6【例2】求兩個(gè)整數(shù)的最大公約數(shù)。數(shù)學(xué)建模：輾轉(zhuǎn)相除法是根據(jù)遞推策略設(shè)計(jì)的。設(shè)ab且a/b=x.c；則a-bx=c，a、b的最大公約數(shù)也是c的約數(shù),則a、b的最大公約數(shù)與b、c的最大公約數(shù)相同。 b/c=x1.c1 =

4、b-cx1=c1 ，直到余數(shù)為0時(shí)，除數(shù)即為所求的最大公約數(shù)。算法設(shè)計(jì)：循環(huán)“不變式”第一次是求a、b相除的余數(shù)c，第二次還是求“a”“b” 相除的余數(shù)，經(jīng)a=b,b=c操作，就實(shí)現(xiàn)了第二次還是求“a”“b” 相除的余數(shù)，這就找到了循環(huán)不變式。循環(huán)在余數(shù)c為0時(shí)結(jié)束。 8/9/2022 4:03 PM7算法如下：main（） int a, b; input(a,b); if(b=0) print(“data error”); return; else c = a mod b; while（c0） a=b; b=c; c=a mod b; print(b);8/9/2022 4:03 PM84.

5、1.2 倒推法 所謂倒推法：是對(duì)某些特殊問(wèn)題所采用的違反通常習(xí)慣的，從 后向前推解問(wèn)題的方法。如下面的例題，因不同方面的需求而采用了倒推策略?！纠?】猴子吃桃問(wèn)題一只小猴子摘了若干桃子，每天吃現(xiàn)有桃的一半多一個(gè)，到第10天時(shí)就只有一個(gè)桃子了，求原有多少個(gè)桃？數(shù)學(xué)模型：每天的桃子數(shù)為：a10=1, a9=(1+a10)*2, a8=(1+a9)*2,a10=1，遞推公式為：ai=(1+ai+1)*2 i= 9,8,7,618/9/2022 4:03 PM9【例2】 輸出如圖4-1的楊輝三角形（限定用一個(gè)一維數(shù)組完成）。數(shù)學(xué)模型：上下層規(guī)律較明顯，中間的數(shù)等于上行左上、右上兩數(shù)之和。問(wèn)題分析：題目

6、中要求用一個(gè)一維數(shù)組即完成。數(shù)組空間一定是由下標(biāo)從小到大利用的，這樣其實(shí)楊輝三角形是按下圖4-2形式存儲(chǔ)的。若求n層，則數(shù)組最多存儲(chǔ)n個(gè)數(shù)據(jù)。 1 1 1 1 2 1 1 3 3 11 4 6 4 1 圖4-1 楊輝三角形11 11 2 11 3 3 114 6 4 1圖4-2 楊輝三角形存儲(chǔ)格式 算法設(shè)計(jì)： A1 = Ai=1Aj = Aj + Aj-1 j=i-1，i-2，2i行 i-1行 i-1行8/9/2022 4:03 PM10算法如下：main( ) int n,i,j,a100;input(n); print(“1”); print(“換行符”);a1=a2=1;print(a1

7、,a2); print(“換行符”);for (i=3;i1;j=j-1) aj=aj+aj-1; for (j=1;j=i;j=j+1) print(aj); print(“換行符”); 11 11 2 11 3 3 114 6 4 18/9/2022 4:03 PM11【例3】穿越沙漠問(wèn)題 用一輛吉普車穿越1000公里的沙漠。吉普車的總裝油量為500加侖，耗油率為1加侖/公里。由于沙漠中沒(méi)有油庫(kù)，必須先用這輛車在沙漠中建立臨時(shí)油庫(kù)。該吉普車以最少的耗油量穿越沙漠，應(yīng)在什么地方建油庫(kù)，以及各處的貯油量。 問(wèn)題分析： 1）先看一簡(jiǎn)單問(wèn)題：有一位探險(xiǎn)家用5天的時(shí)間徒步 橫穿A、B兩村，兩村間是荒

8、無(wú)人煙的沙漠，如果一 個(gè)人只能擔(dān)負(fù)3天的食物和水，那么這個(gè)探險(xiǎn)家至 少雇幾個(gè)人才能順利通過(guò)沙漠。 8/9/2022 4:03 PM12 A城雇用一人與探險(xiǎn)家同帶3天食物同行一天，然后被雇 人帶一天食物返回，并留一天食物給探險(xiǎn)家，這樣探險(xiǎn) 家正好有3天的食物繼續(xù)前行，并于第三天打電話雇B城 人帶3天食物出發(fā)，第四天會(huì)面他們會(huì)面，探險(xiǎn)家得到一 天的食物赴B城。如圖4-3主要表示了被雇用二人的行程。 A B 圖4-3 被雇用二人的行程 2）貯油點(diǎn)問(wèn)題要求要以最少的耗油量穿越沙漠，即到達(dá)終 點(diǎn)時(shí)，沙漠中的各臨時(shí)油庫(kù)和車的裝油量均為0。這樣只 能從終點(diǎn)開(kāi)始向前倒著推解貯油點(diǎn)和貯油量。8/9/2022 4

9、:03 PM13數(shù)學(xué)模型：根據(jù)耗油量最少目標(biāo)的分析，下面從后向前分段討論。第一段長(zhǎng)度為500公里且第一個(gè)加油點(diǎn)貯油為500加侖。第二段中為了貯備油，吉普車在這段的行程必須有往返。下面討論怎樣走效率高：1）首先不計(jì)方向這段應(yīng)走奇數(shù)次2）每次向前行進(jìn)時(shí)吉普車是滿載。3）要能貯存夠下一加油點(diǎn)的貯油量，路上耗油又最少。8/9/2022 4:03 PM14下圖是滿足以上條件的最佳方案，此段共走3次：第一、二次來(lái)回耗油2/3貯油1/3，第三次耗油1/3貯油2/3，所以第二個(gè)加油點(diǎn)貯油為1000加侖。由于每公里耗油率為1加侖，則此段長(zhǎng)度為500/3公里。第三段與第二段思路相同。下圖是一最佳方案此段共走5次：

10、第一、二次來(lái)回耗油2/5貯油3/5，第三、四次來(lái)回耗油2/5貯油3/5，第五次耗油1/5貯油4/5，第三個(gè)加油點(diǎn)貯油為1500加侖。此段長(zhǎng)度為500/5。 500/5公里 第二 第三 終點(diǎn)貯油點(diǎn)（500）貯油點(diǎn)（1000）貯油點(diǎn)（1500）圖4-4 貯油點(diǎn)及貯油量示意8/9/2022 4:03 PM15綜上分析，從終點(diǎn)開(kāi)始分別間隔 500，500/3，500/5，500/7，（公里）設(shè)立貯油點(diǎn)，直到總距離超過(guò)1000公里。每個(gè)貯油點(diǎn)的油量為500，1000，1500，。算法設(shè)計(jì)：由模型知道此問(wèn)題只需通過(guò)累加算法就能解決。變量說(shuō)明：dis表示距終點(diǎn)的距離，1000- dis則表示距起點(diǎn)的距離，k

11、表示貯油點(diǎn)從后到前的序號(hào)。8/9/2022 4:03 PM16desert（ ） int dis，k，oil,k; dis=500;k=1;oil=500; do print(“storepoint”,k,”distance”,1000-dis,”oilquantity”,oil)； k=k+1; dis=dis+500/(2*k-1); oil= 500*k; while ( dis1000) oil=500*(k-1)+(1000-dis)*( 2*k-1); print(“storepoint”,k,”distance”,0,”oilquantity”,oil)； 8/9/2022 4:

12、03 PM174.1.3 迭代法解方程迭代法解方程的實(shí)質(zhì)是按照下列步驟構(gòu)造一個(gè)序列x0,x1,xn,來(lái)逐步逼近方程f(x)=0的解： 1）選取適當(dāng)?shù)某踔祒0； 2）確定迭代格式，即建立迭代關(guān)系，需要將方程f(x)=0改 寫為x=(x)的等價(jià)形式； 構(gòu)造序列x0，x1，xn，即先求得x1=(x0)，再求 x2=(x1)，如此反復(fù)迭代，就得到一個(gè)數(shù)列x0， x1，xn，若這個(gè)數(shù)列收斂，即存在極值，且函數(shù) (x)連續(xù)，則很容易得到這個(gè)極限值x*就是方程f(x)=0的根。 8/9/2022 4:03 PM18【例1】迭代法求方程組根算法說(shuō)明：方程組解的初值X=（x0，x1，xn-1）,迭代關(guān)系方程組為

13、：xi=gi(X)(i=0,1,n-1),w為解的精度,則算法如下：for(i=0;in;i+)xi=初始近似根;do k=k+1; for(i=0;in;i) yi=xi; for(i=0;in;i+) xi=gi(yi); for(i=0;iw and kmaxn )；for(i=0;i=1e-4); return(x1); 8/9/2022 4:03 PM22 令a0,b0=a,b，c0=(a0+b0)/2，若f(c0)=0，則c0為方程f(x)=0的根；否則，若f(a0)與f(c0)異號(hào)，即 f(a0)*f(c0)0，則令a1,b1=a0,c0；若f(b0)與f(c0)異號(hào)，即 f(b

14、0)*f(c0)0，則令a1,b1=c0,b0。 依此做下去，當(dāng)發(fā)現(xiàn)f(cn)=0時(shí)，或區(qū)間an,bn足夠小，比如| an-bn |0.0001時(shí)，就認(rèn)為找到了方程的根。 用二分法求一元非線性方程f(x)= x3/2+2x2-8=0（其中表示冪運(yùn)算）在區(qū)間0，2上的近似實(shí)根r，精確到0.0001.算法如下：圖4-6 二分法求解 方程示意【例3】二分法求解方程f(x)=0根 用二分法求解方程f(x)=0根的前提條件是：f(x)在求解的區(qū)間a,b上是連續(xù)的，且已知f(a)與f(b)異號(hào)，即f(a)*f(b)0。8/9/2022 4:03 PM23main( ) float x,x1=0,x2=2,

15、f1,f2,f; print(“input a,b (f(a)*f(b)0) printf(No root); return; do x=(x1+x2)/2; f=x*x*x/2+2*x*x-8; if(f=0) break; if(f1*f0.0) x1=x; f1=x1*x1*x1/2+2*x1*x1-8; else x2=x;while(fabs(f)=1e-4);print(root=,x); 8/9/2022 4:03 PM244.2 蠻力法枚舉法其它范例基礎(chǔ)：計(jì)算機(jī)運(yùn)算速度快實(shí)例：選擇排序、冒泡排序、插入排序、順序查找、樸素的字符串匹配、枚舉法、盲目搜索算法8/9/2022 4:0

16、3 PM254.2.1 枚舉法 枚舉（ enumerate）法（窮舉法）根據(jù)問(wèn)題中的條件將可能的情況一一列舉出來(lái)，逐一嘗試從中找出滿足問(wèn)題條件的解。枚舉法設(shè)計(jì)的兩個(gè)方面： 1）找出枚舉范圍：分析問(wèn)題所涉及的各種情況。 2）找出約束條件：分析問(wèn)題的解需要滿足的條件，并用邏輯表達(dá)式表示。8/9/2022 4:03 PM26【例1】百錢百雞問(wèn)題。中國(guó)古代數(shù)學(xué)家張丘建在他的算經(jīng)中提出了著名的“百錢百雞問(wèn)題”：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何?算法設(shè)計(jì)1：設(shè)x，y，z分別為公雞、母雞、小雞的數(shù)量。 嘗試范圍：由題意給定共100錢要買百雞，若全買公雞最多買100

17、/5=20只，顯然x的取值范圍120之間；同理，y的取值范圍在133之間，z的取值范圍在1100之間。 約束條件： x+y+z=100 且 5*x+3*y+z/3=100 8/9/2022 4:03 PM27算法1如下： main( ) int x,y,z; for(x=1;x=20;x=x+1) for(y=1;y=34;y=y+1) for(z=1;z=100;z=z+1) if(100=x+y+z and 100=5*x+3*y+z/3) print(the cock number is,x)； print(the hen number is, y)； print(the chick n

18、umber is z); 算法分析：以上算法需要枚舉嘗試20*34*100=68000次。算法的效率顯然太低8/9/2022 4:03 PM28算法設(shè)計(jì)2：在公雞（x）、母雞（y）的數(shù)量確定后，小雞的數(shù)量z就固 定為100-x-y，無(wú)需再進(jìn)行枚舉了。此時(shí)約束條件只有一個(gè)： 5*x+3*y+z/3=100算法2如下： main( ) int x,y,z;for(x=1;x=20;x=x+1) for(y=1;y=33;y=y+1) z=100-x-y; if(z mod 3=0 and 5*x+3*y+z/3=100)print(the cock number is,x)； print(the

19、hen number is, y)； print(the chick number is z);算法分析：以上算法只需要枚舉嘗試20*33=660次。實(shí)現(xiàn)時(shí)約束條件又限定Z能被3整除時(shí)，才會(huì)判斷“5*x+3*y+z/3=100”。這樣省去了z不整除3時(shí)的算術(shù)計(jì)算和條件判斷，進(jìn)一步提高了算法的效率。 8/9/2022 4:03 PM29【例2】解數(shù)字迷： A B C A B A D D D D D D算法設(shè)計(jì)1：按乘法枚舉1)枚舉范圍為： A：39（A=1，2時(shí)積不會(huì)得到六位數(shù)）,B：09, C：09 六位數(shù)表示為A*10000+B*1000+C*100+A*10+B， 共嘗試700次。2)約束

20、條件為： 每次嘗試，先求六位數(shù)與A的積，再測(cè)試積的各位是否符合條件，若符合則找到了問(wèn)題的解。 測(cè)試積的各位是否相同比較簡(jiǎn)單的方法是，從低位開(kāi)始， 每次都取數(shù)據(jù)的個(gè)位，然后整除10，使高位的數(shù)字不斷變 成個(gè)位，并逐一比較。 8/9/2022 4:03 PM30算法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+)

21、 G2=G1; E1=E1/10; G1= E1 mod 10; if(G1G2 ) break; if(i=6) print( F，”*”，A，”=”，E); 8/9/2022 4:03 PM31算法說(shuō)明1：算法中對(duì)枚舉出的每一個(gè)五位數(shù)與A相乘，結(jié)果存儲(chǔ)在變量E中。然后，測(cè)試得到的六位數(shù)E是否各個(gè)位的數(shù)字都相同。鑒于要輸出結(jié)果，所以不要改變計(jì)算結(jié)果，而另設(shè)變量E1，用于測(cè)試運(yùn)算。算法分析1：以上算法的嘗試范圍是A：39，B：09， C：09 。共嘗試700次，每次，不是一個(gè)好的算法。算法設(shè)計(jì)2：將算式變形為除法：DDDDDD/A=ABCAB。此時(shí)只需枚舉A：39 D：19，共嘗試7*9=63

22、次。每次嘗試，測(cè)試商的萬(wàn)位、十位與除數(shù)是否相同，千位與個(gè)位是否相同，都相同時(shí)為解。算法2如下:8/9/2022 4:03 PM32main（）int A,B,C,D,E,F; for(A=3;A=9;A+) for(D=1;D=9;D+) E = D*100000+D*10000+D*1000+D*100+D*10+D; if(E mod A=0) F=EA; if(F10000=A and (F mod 100)10=A) if(F1000 mod 10 =F mod 10) print( F，”*”，A，”=”，E); 8/9/2022 4:03 PM334.2.2 其它范例【例3】獄吏問(wèn)

23、題 某國(guó)王對(duì)囚犯進(jìn)行大赦，讓一獄吏n次通過(guò)一排鎖著的n間牢房，每通過(guò)一次，按所定規(guī)則轉(zhuǎn)動(dòng)n間牢房中的某些門鎖, 每轉(zhuǎn)動(dòng)一次, 原來(lái)鎖著的被打開(kāi), 原來(lái)打開(kāi)的被鎖上；通過(guò)n次后，門鎖開(kāi)著的，牢房中的犯人放出，否則犯人不得獲釋。 轉(zhuǎn)動(dòng)門鎖的規(guī)則是這樣的，第一次通過(guò)牢房，要轉(zhuǎn)動(dòng)每一把門鎖，即把全部鎖打開(kāi)；第二次通過(guò)牢房時(shí)，從第二間開(kāi)始轉(zhuǎn)動(dòng)，每隔一間轉(zhuǎn)動(dòng)一次；第k次通過(guò)牢房，從第k間開(kāi)始轉(zhuǎn)動(dòng)，每隔k-1 間轉(zhuǎn)動(dòng)一次；問(wèn)通過(guò)n次后，那些牢房的鎖仍然是打開(kāi)的？8/9/2022 4:03 PM34算法設(shè)計(jì)1：1）用n個(gè)空間的一維數(shù)組an,每個(gè)元素記錄一個(gè)鎖的狀 態(tài)，1為被鎖上，0為被打開(kāi)。2）用數(shù)學(xué)運(yùn)算方便

24、模擬開(kāi)關(guān)鎖的技巧，對(duì)i號(hào)鎖的一次開(kāi) 關(guān)鎖可以轉(zhuǎn)化為算術(shù)運(yùn)算：ai=1-ai。3）第一次轉(zhuǎn)動(dòng)的是1，2，3，n號(hào)牢房； 第二次轉(zhuǎn)動(dòng)的是2，4，6，號(hào)牢房； 第三次轉(zhuǎn)動(dòng)的是3，6，9，號(hào)牢房； 第i次轉(zhuǎn)動(dòng)的是i，2i，3i，4i，號(hào)牢房，是起點(diǎn)為i，公差為i的等差數(shù)列。 4）不做其它的優(yōu)化，用蠻力法通過(guò)循環(huán)模擬獄吏的開(kāi)關(guān) 鎖過(guò)程，最后當(dāng)?shù)趇號(hào)牢房對(duì)應(yīng)的數(shù)組元素ai為0時(shí)，該牢房的囚犯得到大赦。算法1如下： 8/9/2022 4:03 PM35main1( )int *a,i,j,n; input(n); a=calloc(n+1,sizeof(int); for (i=1; i=n;i+) ai=

25、1; for (i=1; i=n;i+) for (j=i; j=n;j=j+i) aj=1-aj; for (i=1; i=n;i+) if (ai=0) print(i,”is free.”);算法分析：以一次開(kāi)關(guān)鎖計(jì)算，算法的時(shí)間復(fù)雜度為n(1+1/2+1/3+1/n)=O(nlogn)。8/9/2022 4:03 PM36問(wèn)題分析：轉(zhuǎn)動(dòng)門鎖的規(guī)則可以有另一種理解，第一次轉(zhuǎn)動(dòng)的是編號(hào)為1的倍數(shù)的牢房；第二次轉(zhuǎn)動(dòng)的是編號(hào)為2的倍數(shù)的牢房；第三次轉(zhuǎn)動(dòng)的是編號(hào)為3的倍數(shù)的牢房；則獄吏問(wèn)題是一個(gè)關(guān)于因子個(gè)數(shù)的問(wèn)題。令d(n)為自然數(shù)n的因子個(gè)數(shù)，這里不計(jì)重復(fù)的因子，如4的因子為1，2，4共三個(gè)因

26、子，而非1，2，2，4。則d(n)有的為奇數(shù)，有的為偶數(shù)，見(jiàn)下表: 表4-3 編號(hào)與因數(shù)個(gè)數(shù)的關(guān)系 n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 d(n) 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 數(shù)學(xué)模型1：上表中的d(n)有的為奇數(shù)，有的為偶數(shù)，由于牢房的門開(kāi)始是關(guān)著的，這樣編號(hào)為i的牢房，所含1i之間的不重復(fù)因子個(gè)數(shù)為奇數(shù)時(shí)，牢房最后是打開(kāi)的，反之，牢房最后是關(guān)閉的。8/9/2022 4:03 PM37算法設(shè)計(jì)2:1）算法應(yīng)該是求出每個(gè)牢房編號(hào)的不重復(fù)的因子個(gè)數(shù)，當(dāng)它為奇數(shù)時(shí)，這里邊的囚犯得到大赦。2）一個(gè)數(shù)的因子是沒(méi)有規(guī)律的，只

27、能從1n枚舉嘗試。算法2如下：main2( )int s,i,j,n; input(n); for (i=1; i=n;i+) s=1; for (j=2; j=i;j=j+) if （i mod j=0） s=s+1; if （s mod 2 =1） print(i,”is free.”); 8/9/2022 4:03 PM38算法分析： 獄吏開(kāi)關(guān)鎖的主要操作是ai=1- ai;共執(zhí)行了n*(1+1/2+1/3+1/n)次，時(shí)間近似為復(fù)雜度為O（n log n）。使用了n個(gè)空間的一維數(shù)組。算法2沒(méi)有使用輔助空間，但由于求一個(gè)編號(hào)的因子個(gè)數(shù)也很復(fù)雜，其主要操作是判斷i mod j是否為0，共執(zhí)

28、行了n*(1+2+3+n)次，時(shí)間復(fù)雜度為O（n2）。 數(shù)學(xué)模型2：仔細(xì)觀察表4-3，發(fā)現(xiàn)當(dāng)且僅當(dāng)n為完全平方數(shù)時(shí),d(n)為奇數(shù)；這是因?yàn)閚的因子是成對(duì)出現(xiàn)的,也即當(dāng)n=a*b且ab時(shí)，必有兩個(gè)因子a，b; 只有n為完全平方數(shù)，也即當(dāng)n=a2時(shí), 才會(huì)出現(xiàn)d(n)為奇數(shù)的情形。算法設(shè)計(jì)3：這時(shí)只需要找出小于n的平方數(shù)即可。算法3如下：8/9/2022 4:03 PM39main3( ) int s,i,j,n; input(n); for (i=1;i=n;i+) if（i*i=n） print(i,”is free.”); else break; 由此算法我們應(yīng)當(dāng)注意：在對(duì)運(yùn)行效率要求較高

29、的大規(guī)模的數(shù)據(jù)處理問(wèn)題時(shí)，必須多動(dòng)腦筋找出效率較高的數(shù)學(xué)模型及其對(duì)應(yīng)的算法。8/9/2022 4:03 PM404.3 分而治之算法分治算法框架二分法二分法變異其它分治方法8/9/2022 4:03 PM414.3.1 分治算法框架 1算法設(shè)計(jì)思想 將整個(gè)問(wèn)題分解成若干個(gè)小問(wèn)題后分而治之。如果分解得到的子問(wèn)題相對(duì)來(lái)說(shuō)還太大，則可反復(fù)使用分治策略將這些子問(wèn)題分成更小的同類型子問(wèn)題，直至產(chǎn)生出方便求解的子問(wèn)題，必要時(shí)逐步合并這些子問(wèn)題的解，從而得到問(wèn)題的解。三個(gè)步驟：1）分解； 2）解決； 3）合并。8/9/2022 4:03 PM422適合用分治法策略的問(wèn)題滿足分治法解決問(wèn)題的條件：1） 能將這

30、n個(gè)數(shù)據(jù)分解成k個(gè)不同子集合，且得到k個(gè)子集合是可以獨(dú)立求解的子問(wèn)題，其中1kn；2） 分解所得到的子問(wèn)題與原問(wèn)題具有相似的結(jié)構(gòu)，便于利用遞歸或循環(huán)機(jī)制；在求出這些子問(wèn)題的解之后，就可以推解出原問(wèn)題的解8/9/2022 4:03 PM43分治法的一般的算法設(shè)計(jì)模式如下：Divide-and-Conquer(int n) /n為問(wèn)題規(guī)模/ if（nn0） /n0 為可解子問(wèn)題的規(guī)模/ 解子問(wèn)題； return(子問(wèn)題的解)； /*分解為較小子問(wèn)題p1,p2,pk*/ for （i=1 ;i=k;i+） yi=Divide-and-Conquer(|Pi|); /遞歸解決Pi/ T =MERGE(

31、y1,y2,.,yk); /合并子問(wèn)題/ return(T); 8/9/2022 4:03 PM444.3.2 二分法當(dāng)每次都將問(wèn)題分解為原問(wèn)題規(guī)模的一半時(shí)，稱為二分法。二分法是分治法較常用的分解策略，數(shù)據(jù)結(jié)構(gòu)課程中的折半查找、歸并排序等算法都是采用此策略實(shí)現(xiàn)的。【例1】金塊問(wèn)題： 老板有一袋金塊(共n塊)，最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。算法設(shè)計(jì)1：比較簡(jiǎn)單的方法是逐個(gè)的進(jìn)行比較查找。先拿兩塊比較重量，留下重的一個(gè)與下一塊比較，直到全部比較完畢，就找到了最重的金子。算法類似于一趟選擇排序8/9/2

32、022 4:03 PM45算法如下： maxmin( float a,int n) max=min=a1; for(i=2 i=n i+ ) if(max ai) min=ai; 算法分析1：算法中需要n-1次比較得到max。最好的情況是金塊是由小到大取出的，不需要進(jìn)行與min的比較，共進(jìn)行n-1次比較。最壞的情況是金塊是由大到小取出的，需要再經(jīng)過(guò)n-1次比較得到min,共進(jìn)行2*n-2次比較。至于在平均情況下，A(i)將有一半的時(shí)間比max大，因此平均比較數(shù)是3(n1)/2。8/9/2022 4:03 PM46算法設(shè)計(jì)2:問(wèn)題可以簡(jiǎn)化為：在含n（n是2的冪（n=2）個(gè)元素的集合中尋找極大元和

33、極小元。用分治法（二分法）可以用較少比較次數(shù)地解決上述問(wèn)題： 1） 將數(shù)據(jù)等分為兩組（兩組數(shù)據(jù)可能差1），目的是分別選取其中的最大（小）值。 2）遞歸分解直到每組元素的個(gè)數(shù)2，可簡(jiǎn)單地找到最大（小）值。 3）回溯時(shí)將分解的兩組解大者取大，小者取小，合并為當(dāng)前問(wèn)題的解。8/9/2022 4:03 PM47算法2 遞歸求取最大和最小元素 float an;maxmin （int i, int j ,float &fmax, float &fmin） int mid; float lmax, lmin, rmax, rmin; if (i=j) fmax= ai; fmin=ai; else if

34、(i=j-1)if(airmax) fmax=lmax; else fmax=rmax; if(lminrmin)fmin=rmin; else fmin=lmin; 8/9/2022 4:03 PM48算法分析：MAXMIN需要的元素比較數(shù)是多少呢？如果用T(n)表示這個(gè)數(shù)，則所導(dǎo)出的遞歸關(guān)系式是:當(dāng)n是2的冪時(shí)，即對(duì)于這個(gè)某個(gè)正整數(shù)k，n=2k，有可以證明，任何以元素比較為基礎(chǔ)的找最大和最小元素的算法，其元素比較下界均為 次。因此，過(guò)程MAXMIN在這種意義上是最優(yōu)的。8/9/2022 4:03 PM49【例2】殘缺棋盤殘缺棋盤是一個(gè)有2k2k （k1）個(gè)方格的棋盤，其中恰有一個(gè)方格殘缺。

35、圖4-7給出k=1時(shí)各種可能的殘缺棋盤，其中殘缺的方格用陰影表示。 號(hào) 號(hào) 號(hào) 號(hào)圖4-7 四種三格板這樣的棋盤我們稱作“三格板”，殘缺棋盤問(wèn)題就是要用這四種三格板覆蓋更大的殘缺棋盤。在此覆蓋中要求：1）兩個(gè)三格板不能重疊2）三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格在這種限制條件下，所需要的三格板總數(shù)為(2k2k -1 )/3。 8/9/2022 4:03 PM50算法設(shè)計(jì)1：分而治之方法解決殘缺棋盤問(wèn)題 1）問(wèn)題分解過(guò)程如下： s=size/2 號(hào)號(hào)號(hào)號(hào)k=1，2，3，4都是如此，k=1為停止條件。 8/9/2022 4:03 PM512）棋盤的識(shí)別 棋盤的規(guī)模是一個(gè)必要的信息，有了

36、這個(gè)信息，只要知道其左上角的左上角方格所在行、列就可以唯一確定一個(gè)棋盤了，殘缺方格或“偽”殘缺方格直接用行、列號(hào)記錄。 tr 棋盤中左上角方格所在行。 tc 棋盤中左上角方格所在列。 dr 殘缺方塊所在行。 dc 殘缺方塊所在列。 size 棋盤的行數(shù)或列數(shù)。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：用二維數(shù)組board ，模擬棋盤。覆蓋殘缺棋盤所需要的三格板數(shù)目為：( size2 -1 ) / 3將這些三格板編號(hào)為1到( s i z e2-1 ) / 3。則將殘缺棋盤三格板編號(hào)的存儲(chǔ)在數(shù)組board 的對(duì)應(yīng)位置中，這樣輸出數(shù)組內(nèi)容就是問(wèn)題的解。結(jié)合圖4-9，理解算法。8/9/2022 4:03 PM52算法如下： in

37、t amount=0; main（） int size=1,x,y; input(k); for (i=1;i=k;i+) size=size*2; print(“input incomplete pane ”); input(x,y); Cover(0, 0, x, y, size); 圖4-9 一個(gè)4*4的殘缺棋盤及其解 8/9/2022 4:03 PM53 Cover(int tr, int tc, int dr, int dc, int size) if (size2) return;int t = amount +, / 所使用的三格板的數(shù)目s=size/2; / 子問(wèn)題棋盤大小 /

38、殘缺方格位于左上棋盤if (dr tr + s & dc tc + s)Cover ( tr, tc, dr, dc, s); Boardtr + s - 1tc + s = t; / 覆蓋號(hào)三格板 Boardtr + stc + s - 1 = t; Boardtr + stc + s = t; Cover (tr, tc+s, tr+s-1, tc+s, s); / 覆蓋其余部分 Cover(tr+s, tc, tr+s, tc+s-1, s); Cover(tr+s, tc+s, tr+s, tc+s, s); 8/9/2022 4:03 PM54else if(dr = tc + s)

39、/殘缺方格位于右上象限Cover ( t r, tc+s, dr, dc, s); Boardtr + s - 1tc + s - 1 = t; / 覆蓋號(hào)三格板 Boardtr + stc + s - 1 = t; Boardtr + stc + s = t; Cover (tr, tc, tr+s-1, tc+s-1, s); /覆蓋其余部分 Cover(tr+s, tc, tr+s, tc+s-1, s); Cover(tr+s, tc+s, tr+s, tc+s, s);/殘缺方格位于覆蓋左下象限 else if (dr = tr + s & dc = tr + s & dc = tc

40、 + s) Cover(tr+s, tc+s, dr, dc, s); Boardtr + s - 1tc + s - 1 = t; / 覆蓋號(hào)三格板 Boardtr + s - 1tc + s = t; Boardtr + stc + s - 1 = t; Cover (tr, tc, tr+s-1, tc+s-1, s); /覆蓋其余部分 Cover (tr, tc+s, tr+s-1, tc+s, s); Cover(tr+s, tc, tr+s, tc+s-1, s); void OutputBoard(int size) for (int i = 0; i size; i+) for

41、 (int j = 0; j size; j+) print( Boardij); print(“換行符”); 算法分析：因?yàn)橐采w(size2 -1)/ 3個(gè)三格板，所以算法的時(shí)間復(fù)雜性為（size2）。 8/9/2022 4:03 PM564.3.3 二分法變異 【例4】大整數(shù)乘法在某些情況下，我們需要處理很大的整數(shù)，它無(wú)法在計(jì)算機(jī)硬件能直接允許的范圍內(nèi)進(jìn)行表示和處理。若用浮點(diǎn)數(shù)來(lái)存儲(chǔ)它，只能近似地參與計(jì)算，計(jì)算結(jié)果的有效數(shù)字會(huì)受到限制。若要精確地表示大整數(shù)，并在計(jì)算結(jié)果中要求精確地得到所有位數(shù)上的數(shù)字，就必須用軟件的方法來(lái)實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算。請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)

42、的乘法運(yùn)算。8/9/2022 4:03 PM57數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：首先用數(shù)組存儲(chǔ)大整數(shù)數(shù)據(jù)，再將兩個(gè)乘數(shù)和積都按由低位到高位逐位存儲(chǔ)到數(shù)組元素中。算法設(shè)計(jì)1：存儲(chǔ)好兩個(gè)高精度數(shù)據(jù)后，模擬豎式乘法，讓兩個(gè)高精度數(shù)據(jù)的按位交叉相乘，并逐步累加即可得到精確的結(jié)果，用二重循環(huán)就可實(shí)現(xiàn)。 8/9/2022 4:03 PM58算法設(shè)計(jì)1：存儲(chǔ)兩個(gè)高精度數(shù)據(jù)，模擬豎式乘法，讓兩個(gè)高精度數(shù)據(jù)的按位交叉相乘，并逐步累加，即可得到精確的計(jì)算結(jié)果。用二重循環(huán)就可控制兩個(gè)數(shù)不同位相乘的過(guò)程。只考慮正整數(shù)的乘法，算法細(xì)節(jié)設(shè)計(jì)如下：1) 按字符型處理，存儲(chǔ)在字符串?dāng)?shù)組s1、s2中，計(jì)算結(jié)果存儲(chǔ)在整型數(shù)組a中。2)通過(guò)字符的A

43、SCII碼，數(shù)字字符可以直接參與運(yùn)算，k位數(shù)字與j位數(shù)字相乘的表達(dá)式為：(s1k-48)*(s2j-48)。3)每一次數(shù)字相乘的結(jié)果位數(shù)是不固定的，而結(jié)果數(shù)組中每個(gè)元素只存儲(chǔ)一位數(shù)字，所以用變量b暫存結(jié)果，若超過(guò)1位數(shù)則進(jìn)位，用變量d存儲(chǔ)。這樣每次計(jì)算的表達(dá)式為： b= ai+(s1k-48)*(s2j-48)+d。8/9/2022 4:03 PM59main( ) long b,c,d; int i,i1,i2,j,k,n,n1,n2,a256; char s1256,s2256; input(s1); input(s2); for (i=0;i255;i+) ai=0; n1=strlen

44、(s1); n2=strlen(s2); d=0; for (i1=0,k=n1-1;i1n1;i1+,k-) for (i2=0,j=n2-1;i20) i=i+1; ai=ai+d mod 10; d=d/10; n=i; for (i=n;i=0;i-) print(ai);8/9/2022 4:03 PM60算法說(shuō)明：循環(huán)變量j、k分別是兩個(gè)乘數(shù)字符串的下標(biāo)。i1表示字符串str1由低位到高位的位數(shù)，范圍0n1-1（與k相同）。i2表示字符串str2由低位到高位的位數(shù)，范圍0n2-1（與j相同）。i表示乘法正在運(yùn)算的位，也是計(jì)算結(jié)果存儲(chǔ)的位置。算法分析1：算法是以n1,n2代表兩個(gè)乘數(shù)

45、的位數(shù)，由算法中的循環(huán)嵌套知，算法的主要操作是乘法，算法的時(shí)間復(fù)雜度是O（n1*n2）。 算法設(shè)計(jì)2：下面?zhèn)冇梅种畏▉?lái)設(shè)計(jì)一個(gè)更有效的大整數(shù)乘積算法。設(shè)計(jì)的重點(diǎn)是要提高乘法算法的效率，設(shè)計(jì)如下：設(shè)X和Y都是n位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積X*Y。圖4-10 大整數(shù)X和Y的分段8/9/2022 4:03 PM61 將n位的二進(jìn)制整數(shù)X和Y各分為2段，每段的長(zhǎng)為n/2位(為簡(jiǎn)單起見(jiàn)，假設(shè)n是2的冪)，如圖4-10所示。顯然問(wèn)題的答案并不是A*C*K1+C*D*K2（K1、K2與A、B、C、D無(wú)關(guān)），也就是說(shuō)，這樣做并沒(méi)有將問(wèn)題分解成兩個(gè)獨(dú)立的子問(wèn)題。按照乘法分配律，分解后的計(jì)算過(guò)程如下：記：

46、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)模型分析：如果按式(1)計(jì)算X*Y，則我們必須進(jìn)行4次n/2位整數(shù)的乘法(AC，AD，BC和BD)，以及3次不超過(guò)n位的整數(shù)加法，此外還要做2次移位 (分別對(duì)應(yīng)于式(1)中乘2n和乘2n/2)。所有這些加法和移位共用O(n)步運(yùn)算。設(shè)T(n)是2個(gè)n位整數(shù)相乘所需的運(yùn)算總數(shù)，則由式(1)，我們有以下(2)式： 8/9/2022 4:03 PM62 T（1）=1 T（n）=4T(n/2)+O(n) （2）由此遞歸式迭代過(guò)程如下：

47、T(n)=4T(n/2)+cn =4(4T(n/22)+cn/21)+cn =42(T(n/23)+ cn/22)+41cn/21+cn = =4 k+4k-1 *2c+4k-2 *4c+4c2k-1+c2k =O（4k）= O(nlog4) =O（n2）所以可得算法的時(shí)間復(fù)雜度為T(n)=O(n2)。8/9/2022 4:03 PM63模型改進(jìn)：X*Y=A*C*2n+(A-B)(D-C)+AC+BD*2n/2+B*D (3)式(3)看起來(lái)比式(1)復(fù)雜，但它僅需做3次n/2位整數(shù)的乘法：AC，BD和(A-B)(D-C)，6次加、減法和2次移位。由此可得: (4)用解遞歸方程的迭代公式法，不妨

48、設(shè)n=2k： T(n)=3T(n/2)+cn =3(3T(n/4)+cn/2)+cn =9(T(n/8)+ cn/4)+3cn/2+cn = =3k +3k-1 *2c+3k-2 *4c+3c2k-1+c2k = O(nlog3)則得到T(n)=O(nlog3)=O(n1.59)。8/9/2022 4:03 PM64MULT(X,Y,n) X和Y為2個(gè)小于2n的整數(shù)，返回結(jié)果為X和Y的乘積XY S=SIGN(X)*SIGN(Y); /S為X和Y的符號(hào)乘積 X=ABS(X); Y=ABS(Y); /X和Y分別取絕對(duì)值 if（ n=1） if (X=1 and Y=1) return(S)； el

49、se return(0)； else A=X的左邊n/2位; B=X的右邊n/2位; C=Y的左邊n/2位; D=Y的右邊n/2位; ml=MULT(A,C,n/2); m2=MULT(A-B,D-C,n/2); m3=MULT(B,D,n/2); S=S*(m1*2n+(m1+m2+m3)*2n/2+m3); return(S); 8/9/2022 4:03 PM65【例】求數(shù)列的最大子段和。給定n個(gè)元素的整數(shù)列（可能有負(fù)整數(shù)）a1,a2,an，求形如：ai,ai+1,aj i,j=1,2,n, i0) return(aleft) ; else return(0);else center=(left+right)/2; left_sum=max_sub_sum(a,left,center); right_sum=max_sub_sum(a,center+1,right); s1=0; lefts=0;8/9/2022 4:03 PM68for (i=center;i=left;i-) lefts=lefts+ai; if( leftss1) s1=lefts;s2=0; rights=0;for( i=