第4章1 迭代蠻力分治

第四章基本的算法策略4.1迭代算法4.2蠻力算法4.3分而治之算法4.4貪婪算法4.5動態(tài)規(guī)劃4.6算法策略間的比較14.1迭代算法4.1.1遞推法4.1.2倒推法4.1.3迭代法解方程24.1.1遞推法

【例1】兔子繁殖問題問題描述：一對兔子從出生后第三個月開始，每月生一對小兔子。小兔子到第三個月又開始生下一代小兔子。假若兔子只生不死，一月份抱來一對剛出生的小兔子，問一年中每個月各有多少只兔子。3問題分析：因一對兔子從出生后第三個月開始每月生一對小兔子，則每月新下小兔子的對數(shù)由前兩個月的小兔子的對數(shù)決定。則繁殖過程如下：一月二月三月四月五月六月……111+1=22+1=33+2=55+3=8……數(shù)學(xué)建模：y1=y2=1yn=yn-1+yn-2n=3，4，5，…4算法1：main(){inti,a=1,b=1;print(a,b);for(i=1;i＜=10;i++){c=a+b;print(c);a=b;b=c；}}5算法2：遞推迭代表達(dá)式123456789abc=a+ba=b+cb=a+cc=a+ba=b+cb=a+c……由此歸納出可以用c=a+b;a=b+c;b=c+a;做循環(huán)不變式。算法2如下：main(){inti,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)。

6遞推迭代表達(dá)式12

3456789aba=a+bb=a+ba=a+bb=a+b……

由此歸納出可以用a=a+b;b=a+b;做循環(huán)不變式，從而得到以下算法3:main(){inti,a=1,b=1;print(a,b);for(i=1;i＜=5;i++){a=a+b;b=a+b;print(a,b);}}算法3：7【例2】求兩個整數(shù)的最大公約數(shù)。數(shù)學(xué)建模：輾轉(zhuǎn)相除法是根據(jù)遞推策略設(shè)計(jì)的。不妨設(shè)兩個整數(shù)a>b且a除以b商x余c；則a-bx=c，不難看出a、b的最大公約數(shù)也是c的約數(shù)(一個數(shù)能整除等式左邊就一定能整除等式的右邊)，則a、b的最大公約數(shù)與b、c的最大公約數(shù)相同。

同樣方法推出b、c的最大公約數(shù)與…,直到余數(shù)為0時，除數(shù)即為所求的最大公約數(shù)。8算法如下：main(){inta,b;input(a,b);c=amodb;while(c<>0){a=b;b=c;c=amodb;}print(b);}94.1.2倒推法

所謂倒推法：是對某些特殊問題所采用的違反通常習(xí)慣的，從后向前推解問題的方法。10【例1】猴子吃桃問題一只小猴子摘了若干桃子，每天吃現(xiàn)有桃的一半多一個，到第10天時就只有一個桃子了，求原有多少個桃？11數(shù)學(xué)模型：每天的桃子數(shù)為：a10=1,a9=(1+a10)*2,a8=(1+a9)*2,……a10=1

遞推公式為：ai=(1+ai+1)*2i=9,8,7,6……1算法如下：main(){inti,a;a=1;for(i=9;i>=1;i=i-1)a=(a+1)*2print(a)；}12【例2】輸出如圖所示的楊輝三角形，限定用一個一維數(shù)組完成。111121133114641

……………

13數(shù)學(xué)模型：上下層規(guī)律較明顯，中間的數(shù)等于上行左上、右上兩數(shù)之和。111121133114641

……………

14算法如下：main(){intn,i,j,a[100];input(n);print("1");print("換行符");a[1]=a[2]=1;print(a[1],a[2]);print("換行符");for(i=3;i<=n;i=i+1){a[1]=a[i]=1;for(j=i-1，j>1，j=j-1)a[j]=a[j]+a[j-1];for(j=1;j<=i;j=j+1)print(a[j]);print("換行符");}}為了算法簡便輸出如下：11112113311

4641……………因?yàn)槭且痪S數(shù)組，只能倒推計(jì)算15【例3】穿越沙漠問題用一輛吉普車穿越1000公里的沙漠。吉普車的總裝油量為500加侖，耗油率為1加侖/公里。由于沙漠中沒有油庫，必須先用這輛車在沙漠中建立臨時油庫。該吉普車以最少的耗油量穿越沙漠，應(yīng)在什么地方建油庫，以及各處的貯油量。

16貯油點(diǎn)問題要求要以最少的耗油量穿越沙漠，即到達(dá)終點(diǎn)時，沙漠中的各臨時油庫和車的裝油量均為0。這樣只能從終點(diǎn)開始向前倒著推解貯油點(diǎn)和貯油量。17數(shù)學(xué)模型：根據(jù)耗油量最少目標(biāo)的分析，下面從后向前分段討論。第一段長度為500公里且第一個加油點(diǎn)貯油為500加侖。第二段中為了貯備油，吉普車在這段的行程必須有往返。下面討論怎樣走效率高：1)首先這段路應(yīng)走奇數(shù)次，保證最后向前走。2)每次向前行進(jìn)時吉普車是滿載。3)要能貯存夠下一加油點(diǎn)的貯油量，路上耗油又最少?！?8下圖是滿足以上條件的最佳方案，此段共走3次：第一、二次來回耗油2/3貯油1/3，第三次耗油1/3貯油2/3，所以第二個加油點(diǎn)貯油為1000加侖。由于每公里耗油率為1加侖，則此段長度為500/3公里。第三段與第二段思路相同。此段共走5次：第一、二次來回耗油2/5貯油3/5，第三、四次來回耗油2/5貯油3/5，第五次耗油1/5貯油4/5，第三個加油點(diǎn)貯油為1500加侖。此段長度為500/5。……

500/5公里<——500/3公里——><——<——500公里——>——>終點(diǎn)<——貯油點(diǎn)(500)<——貯油點(diǎn)(1000)<——貯油點(diǎn)(1500)……12319綜上分析從終點(diǎn)開始分別間隔500，500/3，500/5，500/7，…設(shè)立貯油點(diǎn)，直到總距離超過1000公里。每個貯油點(diǎn)的油量為500，1000，1500，2000…。算法設(shè)計(jì)：

由模型知道此問題并不必用倒推算法解決(只是分析過程用的是倒推法)，只需通過累加算法就能解決。

20變量說明：dis表示距終點(diǎn)的距離，1000-dis則表示距起點(diǎn)的距離，k表示貯油點(diǎn)從后到前的序號。main(){intdis，k，oil,k;dis=500;k=1;oil=500;do{print(“貯油點(diǎn)”,k,“距離”,1000-dis,“貯油量",oil)；k=k+1;dis=dis+500/(2*k-1);oil=500*k;}while(dis<1000)

oil=500*(k-1)+(1000-dis)*(2*k-1);

print("貯油點(diǎn)",k,"距離",0,"貯油量",oil)；}214.1.3迭代法解方程22【例1】牛頓迭代法牛頓迭代法又稱為切線法，它比一般的迭代法有更高的收斂速度。首先,選擇一個接近函數(shù)f(x)零點(diǎn)的x0,計(jì)算相應(yīng)的f(x0)和切線斜率f'(x0)(這里f'表示函數(shù)f的導(dǎo)數(shù))。然后計(jì)算穿過點(diǎn)(x0,f(x0))且斜率為f'(x0)的直線方程為：直線和x軸的交點(diǎn),也就是求如下方程的解：

將新求得交點(diǎn)的x坐標(biāo)命名為x1。通常x1會比x0更接近方程的解。接下來用x1開始下一輪迭代.

牛頓迭代法示意圖23迭代公式可化簡為：此公式就是有名的牛頓迭代公式。已經(jīng)證明,如果f'是連續(xù)的,并且待求的零點(diǎn)x是孤立的,那么在零點(diǎn)x周圍存在一個區(qū)域,只要初始值x0位于這個鄰近區(qū)域內(nèi),那么牛頓法必定收斂。

下面給出用牛頓迭代法，求形如ax^3+bx^2+cx+d=0方程根的算法，系數(shù)a、b、c、d的值依次為1、2、3、4，由主函數(shù)輸入。求x在1附近的一個實(shí)根。求出根后由主函數(shù)輸出。24main(){floata,b,c,d,fx;print("輸入系數(shù)a,b,c,d:");input(a,b,c,d);fx=f(a,b,c,d);printf("方程的根為：",fx);}

floatf(a,b,c,d)floata,b,c,d;{floatx1=1,x0,f0,f1;do{x0=x1;f0=((a*x0+b)*x0+c)*x0+d;f1=(3*a*x0+2*b)*x0+c;x1=x0-f0/f1;}while(fabs(x1-x0)>=1e-4);return(x1);}25二分法求解方程示意【例3】二分法求解方程f(x)=0根

用二分法求解方程f(x)=0根的前提條件是：f(x)在求解的區(qū)間[a,b]上是連續(xù)的，且已知f(a)與f(b)異號，即f(a)*f(b)<026令[a0,b0]=[a,b]，c0=(a0+b0)/2，若f(c0)=0，則c0為方程f(x)=0的根；否則，若f(a0)與f(c0)異號，即f(a0)*f(c0)<0，則令[a1,b1]=[a0,c0]；若f(b0)與f(c0)異號，即f(b0)*f(c0)<0，則令[a1,b1]=[c0,b0]。依此做下去，當(dāng)發(fā)現(xiàn)f(cn)=0時，或區(qū)間[an,bn]足夠小，比如|an-bn|<0.0001時，就認(rèn)為找到了方程的根。

用二分法求一元非線性方程f(x)=x^3/2+2x^2-8=0(其中^表示冪運(yùn)算)在區(qū)間[0，2]上的近似實(shí)根r，精確到0.0001.算法如下：

二分法求解方程示意27main(){floatx,x1=0,x2=2,f1,f2,f;f1=x1*x1*x1/2+2*x1*x1-8;f2=x2*x2*x2/2+2*x2*x2-8;if(f1*f2>0){printf("Noroot");return;}do{x=(x1+x2)/2;f=x*x*x/2+2*x*x-8;if(f=0)break;if(f1*f>0.0){x1=x;f1=f;}elsex2=x;}while(fabs(f)>=1e-4);print("root=",x);}二分法求解方程示意284.2蠻力法

蠻力法是基于計(jì)算機(jī)運(yùn)算速度快這一特性，在解決問題時采取的一種“懶惰”的策略。這種策略不經(jīng)過(或者說是經(jīng)過很少的)思考，把問題的所有情況或所有過程交給計(jì)算機(jī)去一一嘗試，從中找出問題的解。蠻力策略的應(yīng)用很廣，具體表現(xiàn)形式各異，數(shù)據(jù)結(jié)構(gòu)課程中學(xué)習(xí)的：選擇排序、冒泡排序、插入排序、順序查找、樸素的字符串匹配等，都是蠻力策略具體應(yīng)用。比較常用還有枚舉法、盲目搜索算法等，本節(jié)介紹枚舉法和其它一些小的范例，第五章介紹盲目搜索算法。

294.2.1枚舉法

枚舉(enumerate)法(窮舉法)是蠻力策略的一種表現(xiàn)形式，也是一種使用非常普遍的思維方法。它是根據(jù)問題中的條件將可能的情況一一列舉出來，逐一嘗試從中找出滿足問題條件的解。但有時一一列舉出的情況數(shù)目很大，如果超過了我們所能忍受的范圍，則需要進(jìn)一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數(shù)目。用枚舉法解決問題，通?？梢詮膬蓚€方面進(jìn)行算法設(shè)計(jì)：1)找出枚舉范圍：分析問題所涉及的各種情況。2)找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達(dá)式表示。30【例1】百錢百雞問題。中國古代數(shù)學(xué)家張丘建在他的《算經(jīng)》中提出了著名的"百錢百雞問題"：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何?

31算法設(shè)計(jì)1：通過對問題的理解，讀者可能會想到列出兩個三元一次方程，去解這個不定解方程，就能找出問題的解。這確實(shí)是一種辦法，但這里我們要用"懶惰"的枚舉策略進(jìn)行算法設(shè)計(jì)：

設(shè)x，y，z分別為公雞、母雞、小雞的數(shù)量。嘗試范圍：由題意給定共100錢要買百雞，若全買公雞最多買100/5=20只，顯然x的取值范圍1~20之間；同理，y的取值范圍在1~33之間，z的取值范圍在1~100之間。約束條件：x+y+z=100且5*x+3*y+z/3=100

32算法1如下：

main()

{intx,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+zand100=5*x+3*y+z/3)

{print(thecocknumberis",x)；print(thehennumberis",y)；print(thechicknumberis"z);}

}33算法分析：以上算法需要枚舉嘗試20*34*100=68000次。算法的效率顯然太低算法設(shè)計(jì)2：在公雞(x)、母雞(y)的數(shù)量確定后，小雞

的數(shù)量

z就固定為100-x-y，無需再進(jìn)行枚舉了此時約束條件只有一個：

5*x+3*y+z/3=100

34main()

{

intx,y,z;

for(x=1;x<=20;x=x+1)

for(y=1;y<=33;y=y+1)

{

z=100-x-y;

if(zmod3=0and5*x+3*y+z/3=100)

{print(thecocknumberis",x)；print(thehennumberis",y)；print(thechicknumberis"z);}

}

}算法分析：以上算法只需要枚舉嘗試20*33=660次。實(shí)現(xiàn)時約束條件又限定Z能被3整除時，才會判斷"5*x+3*y+z/3=100"。這樣省去了z不整除3時的算術(shù)計(jì)算和條件判斷，進(jìn)一步提高了算法的效率。35【例2】解數(shù)字迷：ABCAB

×ADDDDDD算法設(shè)計(jì)1：按乘法枚舉1)枚舉范圍為：A：3——9(A=1，2時積不會得到六位數(shù)),B：0——9,C：0——9五位數(shù)表示為A*10000+B*1000+C*100+A*10+B共嘗試700次。362)約束條件為：每次嘗試，先求五位數(shù)與A的積，再測試積的各位是否相同，若相同則找到了問題的解。測試積的各位是否相同比較簡單的方法是，從低位開始，每次都取數(shù)據(jù)的個位，然后整除10，使高位的數(shù)字不斷變成個位，并逐一比較。

37算法1如下：main(){intA,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=E1mod10;for(i=1;i<=5;i++){G2=G1;E1=E1\10;G1=E1mod10;if(G1<>G2)break;}if(i=6)print(F，"*"，A，"="，E);}}38算法分析1：以上算法的嘗試范圍是A：3-9，B：0-9，C：0-9。共嘗試700次，每次，不是一個好的算法。算法設(shè)計(jì)2：將算式變形為除法：DDDDDD/A=ABCAB。此時只需枚舉A：3-9D：1-9，共嘗試7*9=63次。每次嘗試測試商的萬位、十位與除數(shù)是否相同，千位與個位是否相同，都相同時為解。39main(){intA,B,C,D,E,F;for(D=1;D<=9;D++){E=D*100000+D*10000+D*1000+D*100+D*10+D;for(A=3;A<=9;A++){if(EmodA=0){F=E\A;if(F\10000=Aand(Fmod100)\10=A)

if(F\1000mod10=Fmod10)print(F，"*"，A，"="，E);}}}}40【例3】獄吏問題某國王對囚犯進(jìn)行大赦，讓一獄吏n次通過一排鎖著的n間牢房，每通過一次，按所定規(guī)則轉(zhuǎn)動n間牢房中的某些門鎖,每轉(zhuǎn)動一次,原來鎖著的被打開,原來打開的被鎖上；通過n次后，門鎖開著的，牢房中的犯人放出，否則犯人不得獲釋。轉(zhuǎn)動門鎖的規(guī)則是這樣的，第一次通過牢房，要轉(zhuǎn)動每一把門鎖，即把全部鎖打開；第二次通過牢房時，從第二間開始轉(zhuǎn)動，每隔一間轉(zhuǎn)動一次；第k次通過牢房，從第k間開始轉(zhuǎn)動，每隔k-1間轉(zhuǎn)動一次；問通過n次后，那些牢房的鎖仍然是打開的？41算法設(shè)計(jì)1：1)用一維數(shù)組a[n],每個元素記錄一個鎖的狀態(tài)，1為被鎖上，0為被打開。2)對i號鎖的一次開關(guān)鎖可轉(zhuǎn)化為運(yùn)算：a[i]=1-a[i]。3)第一次轉(zhuǎn)動的是1，2，3，……，n號牢房；第二次轉(zhuǎn)動的是2，4，6，……號牢房；第三次轉(zhuǎn)動的是3，6，9，……號牢房；……4)用蠻力法通過循環(huán)模擬獄吏的開關(guān)鎖過程，最后當(dāng)?shù)趇號牢房對應(yīng)的數(shù)組元素a[i]為0時，該牢房的囚犯得到大赦。42main(){inta[100],i,j,n;input(n);for(i=1;i<=n;i++)a[i]=1;for(i=1;i<=n;i++)for(j=i;j<=n;j=j+i)a[i]=1-a[i];for(i=1;i<=n;i++)if(a[i]=0)print(i,"isfree.");}算法分析：算法的時間復(fù)雜度為n*(1+1/2+1/3+……+1/n)=O(nlogn)。43問題分析：轉(zhuǎn)動門鎖的規(guī)則可以有另一種理解，第一次轉(zhuǎn)動的是編號為1的倍數(shù)的牢房；第二次轉(zhuǎn)動的是編號為2的倍數(shù)的牢房；第三次轉(zhuǎn)動的是編號為3的倍數(shù)的牢房；……則獄吏問題是一個關(guān)于因子個數(shù)的問題。令d(n)為自然數(shù)n的因子個數(shù)，這里不計(jì)重復(fù)的因子，如4的因子為1，2，4共三個因子，而非1，2，2，4。則d(n)有的為奇數(shù)，有的為偶數(shù)，見下表:編號與因數(shù)個數(shù)的關(guān)系n12345678910111213141516……d(n)1223242434262445……

數(shù)學(xué)模型2：上表中的d(n)有的為奇數(shù)，有的為偶數(shù)，由于牢房的門開始是關(guān)著的，這樣編號為i的牢房，所含因子個數(shù)為奇數(shù)時，牢房最后是打開的，反之，牢房最后是關(guān)閉的。44算法設(shè)計(jì)2:main(){ints,i,j,n;input(n);for(i=1;i<=n;i++){s=1;for(j=2;j<=i;j=j++)if(imodj=0)s=s+1;if(smod2=1)print(i,"isfree.");}}45算法分析：算法1的時間近似為復(fù)雜度為O(nlogn)。使用了n個空間的一維數(shù)組。算法2沒有使用輔助空間，但由于求一個編號的因子個數(shù)也很復(fù)雜，其主要操作是判斷imodj是否為0，共執(zhí)行了n*(1+2+3+……+n)次，時間復(fù)雜度為O(n2)。

46數(shù)學(xué)模型3：仔細(xì)觀察下表，發(fā)現(xiàn)當(dāng)且僅當(dāng)n為完全平方數(shù)時,d(n)為奇數(shù)；這是因?yàn)閚的因子是成對出現(xiàn)的,也即當(dāng)n=a*b且a≠b時，必有兩個因子a，b;只有n為完全平方數(shù)，也即當(dāng)n=a2時,才會出現(xiàn)d(n)為奇數(shù)的情形。算法設(shè)計(jì)3：這時只需要找出小于n的平方數(shù)即可。47main(){ints,i,j,n;input(n);for(i=1;i<=n;i++)if(i*i<=n)print(i*i,"isfree.");elsebreak;}

在對運(yùn)行效率要求較高的大規(guī)模的數(shù)據(jù)處理問題時，必須多動腦筋找出效率較高的數(shù)學(xué)模型及其對應(yīng)的算法。484.3分而治之算法4.3.1分治算法概述4.3.2二分法4.3.3二分法變異4.3.4其它分治方法494.3.1分治算法概述

1.算法設(shè)計(jì)思想分治法求解問題的過程是，將整個問題分解成若干個小問題后分而治之。如果分解得到的子問題相對來說還太大，則可反復(fù)使用分治策略將這些子問題分成更小的同類型子問題，直至產(chǎn)生出方便求解的子問題，必要時逐步合并這些子問題的解，從而得到問題的解。50分治法的基本步驟在每一層遞歸上都有三個步驟：1)分解：將原問題分解為若干個規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題；

2)解決：若子問題規(guī)模較小而容易被解決則直接解，否則再繼續(xù)分解為更小的子問題，直到容易解決；

3)合并：將已求解的各個子問題的解，逐步合并為原問題的解。51有時問題分解后，不必求解所有的子問題，也就不必作第三步的操作。比如折半查找，在判別出問題的解在某一個子問題中后，其它的子問題就不必求解了。分治法的這類應(yīng)用，又稱為"減治法"。多數(shù)問題需要所有子問題的解，并由子問題的解，使用恰當(dāng)?shù)姆椒ê喜⒊蔀檎麄€問題的解，比如合并排序，就是不斷將子問題中已排好序的解合并成較大規(guī)模的有序子集。

522.適合用分治法策略的問題當(dāng)求解一個規(guī)模相當(dāng)大的問題時，用蠻力策略效率一般得不到保證。若問題能滿足以下幾個條件，就能用分治法來提高解決問題的效率。1)

能將n個數(shù)據(jù)分解成k個不同子集合，且得到的k個子集合是可以獨(dú)立求解的子問題；2)

分解所得到的子問題與原問題具有相似的結(jié)構(gòu)，便于利用遞歸或循環(huán)機(jī)制；在求出這些子問題的解之后，就可以推解出原問題的解；

534.3.2典型二分法當(dāng)每次都將問題分解為原問題規(guī)模的一半時，稱為二分法。二分法是分治法較常用的分解策略，數(shù)據(jù)結(jié)構(gòu)課程中的折半查找、歸并排序等算法都是采用此策略實(shí)現(xiàn)的。54【例1】金塊問題：

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

maxmin(floata[],intn,float&max,float&min){max=min=a[1];

for(i=2i<=ni++)

if(max<a[i])max=a[i];elseif(min>a[i])min=a[i];

}56算法分析1：

算法中需要n-1次比較得到max。最好的情況是金塊是由小到大取出的，不需要進(jìn)行與min的比較，共進(jìn)行n-1次比較。最壞的情況是金塊是由大到小取出的，需要再經(jīng)過n-1次比較得到min,共進(jìn)行2*(n-1)次比較。至于在平均情況下，A(i)將有一半的時間比max大，因此平均比較數(shù)是3*(n-1)/2。

57算法設(shè)計(jì)2:用二分法可以用較少比較次數(shù)地解決上述問題：1)

將數(shù)據(jù)等分為兩組(兩組數(shù)據(jù)可能差1)，目的是分別選取其中的最大(小)值。2)

遞歸分解直到每組元素的個數(shù)≤2，可簡單地找到最大(小)。3)

回溯時將分解的兩組解大者取大，小者取小，合并為當(dāng)前問題的解。

58算法2遞歸求取最大和最小元素floata[n];maxmin(inti,intj,float&fmax,float&fmin){intmid;floatlmax,lmin,rmax,rmin;

if(i=j){fmax=a[i];fmin=a[i];}

elseif(i=j-1)if(a[i]<a[j]){fmax=a[j]；fmin=a[i];}

else{fmax=a[i];fmin=a[j];}

else{mid=(i+j)/2;

maxmin(i，mid，lmax，lmin);

maxmin(mid+1，j，rmax，rmin);

if(lmax>rmax)fmax=lmax;elsefmax=rmax;

if(lmin>rmin)fmin=rmin;elsefmin=lmin;

}594.3.3二分法不相似情況對一維數(shù)據(jù)進(jìn)行二分法分解，得到兩個獨(dú)立子問題。對二維問題的二分法分解，會得到幾個獨(dú)立的子問題呢？60【例1】殘缺棋盤殘缺棋盤是一個有2k×2k(k≥1)個方格的棋盤，其中恰有一個方格殘缺。下圖給出k=1時各種可能的殘缺棋盤，其中殘缺的方格用陰影表示。

①號②號③號④號四種三格板這樣的棋盤我們稱作"三格板"，殘缺棋盤問題就是要用這四種三格板覆蓋更大的殘缺棋盤。在此覆蓋中要求：1)兩個三格板不能重疊2)三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格在這種限制條件下，所需要的三格板總數(shù)為(2k×2k-1)/3。

61算法設(shè)計(jì)：下面用分而治之方法解決殘缺棋盤問題。1)以k=2時的問題為例，用二分法進(jìn)行分解，得到的是如下圖，用雙線劃分的四個k=1的棋盤。但要注意這四個棋盤，并不都是與原問題相似且獨(dú)立的子問題。因?yàn)楫?dāng)如圖中的殘缺方格在左上部時，第1個子問題與原問題相似，而右上角、左下角和右下角三個子棋盤(也就是圖中標(biāo)識為2、3、4號子棋盤)，并不是原問題的相似子問題，自然也就不能獨(dú)立求解了。當(dāng)使用一個①號三格板(圖中陰影)覆蓋2、3、4號三個子棋盤的各一個方格后，我們把覆蓋后的方格，也看作是殘缺方格(稱為"偽"殘缺方格)，這時的2、3、4號子問題就是獨(dú)立且與原問題相似的子問題了。

62從以上例子還可以發(fā)現(xiàn)，當(dāng)殘缺方格在第1個子棋盤，用①號三格板覆蓋其余三個子棋盤的交界方格，可以使另外三個子棋盤轉(zhuǎn)化為獨(dú)立子問題；同樣地當(dāng)殘缺方格在第2個子棋盤時，則首先用②號三格板進(jìn)行棋盤覆蓋，當(dāng)殘缺方格在第3個子棋盤時，則首先用③號三格板進(jìn)行棋盤覆蓋，當(dāng)殘缺方格在第4個子棋盤時，則首先用④號三格板進(jìn)行棋盤覆蓋，這樣就使另外三個子棋盤轉(zhuǎn)化為獨(dú)立子問題。同樣地k=1，2，3，4……都是如此，k=1為停止條件。

632)棋盤的識別子棋盤的左上角的方格所在行、列,加上子棋盤的大小，就可以唯一確定一個子棋盤。殘缺方格或“偽”殘缺方格直接用行、列號記錄。?tr棋盤中左上角方格所在行。?tc棋盤中左上角方格所在列。?dr殘缺方塊所在行。?dl殘缺方塊所在列。?size棋盤的大?。葱袛?shù)或列數(shù)）。64數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：

用二維數(shù)組board[][]模擬棋盤。覆蓋殘缺棋盤所需要的三格板數(shù)目為：(size2-1)/3。將這些三格板編號為1到(size2-1)/3。將三格板編號存儲在數(shù)組board[][]的對應(yīng)位置，這樣輸出數(shù)組內(nèi)容就是問題的解。65算法如下：intamount=0,Board[100][100];main(){intsize=1,x,y;input(k);for(i=1;i<=k;i++)size=size*2;print("inputincompletepane");input(x,y);Cover(0,0,x,y,size);OutputBoard(size);}66Cover(inttr,inttc,intdr,intdc,intsize){ints,t;if(size<2)return;amount=amount+1t=amount;//所使用的三格板的數(shù)目s=size/2;//子問題棋盤大小

if(dr<tr+s&&dc<tc+s)//殘缺方格位于左上棋盤｛Cover(tr,tc,dr,dc,s);Board[tr+s-1][tc+s]=t;//覆蓋１號三格板Board[tr+s][tc+s-1]=t;Board[tr+s][tc+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);｝67

elseif(dr<tr+s&&dc>=tc+s)//殘缺方格位于右上象限｛Cover(tr,tc+s,dr,dc,s);Board[tr+s-1][tc+s-1]=t;//覆蓋２號三格板Board[tr+s][tc+s-1]=t;Board[tr+s][tc+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);}

elseif(dr>=tr+s&&dc<tc+s)//殘缺方格位于覆蓋左下｛Cover(tr+s,tc,dr,dc,s);Board[tr+s-1][tc+s-1]=t;//覆蓋３號三格板Board[tr+s-1][tc+s]=t;Board[tr+s][tc+s]=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+s,tr+s,tc+s,s);｝68

elseif(dr>=tr+s&&dc>=tc+s)//殘缺方格位于右下象限｛Cover(tr+s,tc+s,dr,dc,s);Board[tr+s-1][tc+s-1]=t;//覆蓋４號三格板Board[tr+s-1][tc+s]=t;Board[tr+s][tc+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);｝}voidOutputBoard(intsize){for(inti=0;i<size;i++){for(intj=0;j<size;j++)print(Board[i][j]);print("換行符");}}算法分析：因?yàn)橐采w(size2-1)/3個三格板，所以算法的時間復(fù)雜性為Ｏ(size2)。

694.3.4二分法不獨(dú)立情況

【例1】求數(shù)列的最大子段和給定n個整數(shù)a1,a2,…an。求ai…aj的子段，使其和最大。當(dāng)所有整數(shù)為負(fù)數(shù)時定義其最大子段和為0。如-2，11，-4，13，-5，-2，最大子段和為2070問題分析：若用二分法將實(shí)例中的數(shù)據(jù)分解為兩組(-2,11,-4),(13,-5,-2)，第一個子問題的解是11，第二個子問題的解是13，兩個子問題的解不能簡單地得到原問題的解。由此看出這個問題不能分解用二分法成解為獨(dú)立的兩個子問題，子問題中間還有公共的子問題，這類問題稱為子問題重疊類的問題。

那么，怎樣解決這類問題呢？下面我們用二分法解決這類問題中的一些簡單問題，學(xué)習(xí)一下如何處理不獨(dú)立的子問題。71算法設(shè)計(jì)：

分解方法采用二分法，雖然分解后的子問題并不獨(dú)立，但通過對重疊的子問題進(jìn)行專門處理，并對所有子問題合并進(jìn)行設(shè)計(jì)，就可以用二分策略解決此題。72如果將所給的序列a[1..n]分為長度相等的2段a[1-(n/2)]和a[(n/2)+1-n],分別求出這2段的最大子段和,則a[1..n]的最大子段和有3種情形。1)a[1..n]的最大子段和與a[1..(n/2)]的最大子段和相同;2)a[1..n]的最大子段和與a[(n/2)+1..n]的最大子段和相同;3)a[1..n]的最大子段和為a[i..j],且1≤i≤(n/2),(n/2),(n/2)+1≤j≤n。情況1)和情況2)可分別遞歸求得。對于情況3),a[(n/2)]與a[(n/2)+1]一定在最優(yōu)子序列中。因此,我們可以計(jì)算出a[i..(n/2)]的最大值s1;并計(jì)算出a[(n/2)+1..j]中的最大值s2。則s1+s2即為出現(xiàn)情況3)時的最優(yōu)值。73算法如下：MaxSubSum(inta[],intleft,intright){intcenter,i,j,sum,leftsum,rightsum,s1,s2,lefts,rights;if(left=right){if(a[left]>0)return(a[left]);elsereturn(0);}else{center=(left+right)\2;

leftsum=MaxSubSum(a,left,center);rightsum=MaxSubSum(a,center+1,right);s1=0;/處理情形3/lefts=0;74for(i=center;i>=left;i--){lefts=lefts+a[i];if(lefts>s1)s1=lefts;}s2=0;rights=0;for(i=center+1;i<=right;i++){rights=rights+a[i];if(rights>s2)s2=rights;}

if(s1+s2<leftsumandrightsum<left_sum)rturn(leftsum);if(s1+s2<rightsum)return(rightsum);return(s1+s2);}}754.3.5

非等分分治

以上的例子都是用二分策略把問題分解為與原問題相似的子問題。下面看幾個用非等分二分法解決問題的例子。選擇問題就是從一組數(shù)中選擇的第k小的數(shù)據(jù)，這個問題的一個應(yīng)用就是尋找中值元素，此時k=[n/2]。中值是一個很有用的統(tǒng)計(jì)量，例如中間工資，中間年齡，中間重量等。k取其他值也是有意義的，例如，通過尋找第k=n/2、k=n/3和k=n/4的年齡,可將人口進(jìn)行劃分，了解人口的分布情況。

76這個問題可以通過排序來解決，但根據(jù)《數(shù)據(jù)結(jié)構(gòu)》課程的經(jīng)驗(yàn)，最好的排序算法的復(fù)雜性也是O(n*log(n))，下面我們要利用分治法，找到復(fù)雜性為O(n)的算法。但這個問題不能用簡單的二分法分解成完全獨(dú)立、相似的兩個子問題。因?yàn)樵谶x出分解后第一組的第k小的數(shù)據(jù)和第二組的第k小的數(shù)據(jù)，不能保證在這兩個數(shù)據(jù)之一是原問題的解。77【例1】選擇問題1：求一組數(shù)的第二小的數(shù)。

算法設(shè)計(jì)：這個問題不能用簡單的二分法分解成相似的兩個子問題。因?yàn)樵谶x出分解后第一組的第二小的數(shù)據(jù)和第二組的第二小的數(shù)據(jù)，不能保證在這兩個數(shù)據(jù)之一是原問題的解。但是，可以在兩個子集中分別選出最小的兩個數(shù)，共得到4個數(shù)，則第二小的數(shù)在這4個數(shù)中。78floata[n];second(inti,intj，float&fmin2,&fmin1)

{floatlmin2,lmin1,rmin2,rmin;intmid;