基本的算法策略

4.1迭代算法4.1.1遞推法4.1.2倒推法4.1.3迭代法解方程4．1．1遞推法【例1】兔子繁殖問題問題描述：一對(duì)兔子從出生后第三個(gè)月開始，每月生一對(duì)小兔子。小兔子到第三個(gè)月又開始生下一代小兔子。假若兔子只生不死，一月份抱來(lái)一對(duì)剛出生的小兔子，問一年中每個(gè)月各有多少只兔子。問題分析：因一對(duì)兔子從出生后第三個(gè)月開始每月生一對(duì)小兔子，則每月新下小兔子的對(duì)兒數(shù)(用斜體數(shù)字表示)顯然由前兩個(gè)月的小兔子的對(duì)兒數(shù)決定。則繁殖過(guò)程如下：一月二月三月四月五月六月……111+1=22+1=33+2=55+3=8……算法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；

}}數(shù)學(xué)建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，……。算法2：

表4-1遞推迭代表達(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)。

表4-2遞推迭代表達(dá)式123456789aba=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：【例2】求兩個(gè)整數(shù)的最大公約數(shù)。數(shù)學(xué)建模：輾轉(zhuǎn)相除法是根據(jù)遞推策略設(shè)計(jì)的。不妨設(shè)兩個(gè)整數(shù)a>b且a除以b商x余c；則a-bx=c，不難看出a、b的最大公約數(shù)也是c的約數(shù)（一個(gè)數(shù)能整除等式左邊就一定能整除等式的右邊），則a、b的最大公約數(shù)與b、c的最大公約數(shù)相同。同樣方法推出b、c的最大公約數(shù)與……，直到余數(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é)束。

算法如下：main（）{inta,b;input(a,b);if(b=0)

{print(“dataerror”);return;}else{c=amodb;whilec<>0{a=b;

b=c;

c=amodb;}}print(b);}4.1.2倒推法

所謂倒推法：是對(duì)某些特殊問題所采用的違反通常習(xí)慣的，從后向前推解問題的方法。如下面的例題，因不同方面的需求而采用了倒推策略。例1在不知前提條件的情況下，經(jīng)過(guò)從后向前遞推，從而求解問題。即由結(jié)果倒過(guò)來(lái)推解它的前提條件。又如例2由于存儲(chǔ)的要求，而必須從后向前進(jìn)行推算。另外，在對(duì)一些問題進(jìn)行分析或建立數(shù)學(xué)模型時(shí)，從前向后分析問題感到比較棘手，而采用倒推法（如例3），則問題容易理解和解決。下面分別看這幾個(gè)例子：【例1】猴子吃桃問題一只小猴子摘了若干桃子，每天吃現(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)*2I=9,8,7,6……1算法如下：

main(){inti,s;s=1;for(i=9;i>=1;i=i-1)s=(s+1)*2print(s)；

}【例2】輸出如圖4-1的楊輝三角形（限定用一個(gè)一維數(shù)組完成）。數(shù)學(xué)模型：上下層規(guī)律較明顯，中間的數(shù)等于上行左上、右上兩數(shù)之和。問題分析：題目中要求用一個(gè)一維數(shù)組即完成。數(shù)組空間一定是由下標(biāo)從小到大利用的，這樣其實(shí)楊輝三角形是按下圖4-2形式存儲(chǔ)的。若求n層，則數(shù)組最多存儲(chǔ)n個(gè)數(shù)據(jù)。111121133114641

……………

圖4-1楊輝三角形11112113311

4641……………圖4-2楊輝三角形存儲(chǔ)格式

算法設(shè)計(jì)：

A[1]=A[i]=1A[j]=A[j]+A[j-1]j=i-1，i-2，……，2i行i-1行i-1行算法如下：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(“換行符”);}}【例3】穿越沙漠問題用一輛吉普車穿越1000公里的沙漠。吉普車的總裝油量為500加侖，耗油率為1加侖/公里。由于沙漠中沒有油庫(kù)，必須先用這輛車在沙漠中建立臨時(shí)油庫(kù)。該吉普車以最少的耗油量穿越沙漠，應(yīng)在什么地方建油庫(kù)，以及各處的貯油量。

問題分析：

1）先看一簡(jiǎn)單問題：有一位探險(xiǎn)家用5天的時(shí)間徒步橫穿A、B兩村，兩村間是荒無(wú)人煙的沙漠，如果一個(gè)人只能擔(dān)負(fù)3天的食物和水，那么這個(gè)探險(xiǎn)家至少雇幾個(gè)人才能順利通過(guò)沙漠。

A城雇用一人與探險(xiǎn)家同帶3天食物同行一天，然后被雇人帶一天食物返回，并留一天食物給探險(xiǎn)家，這樣探險(xiǎn)家正好有3天的食物繼續(xù)前行，并于第三天打電話雇B城人帶3天食物出發(fā)，第四天會(huì)面他們會(huì)面，探險(xiǎn)家得到一天的食物赴B城。如圖4-3主要表示了被雇用二人的行程。

AB

圖4-3被雇用二人的行程

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

<———500/3公里———><———<———500公里第一———>第二———>第三終點(diǎn)<——貯油點(diǎn)（500）<——貯油點(diǎn)（1000）<———貯油點(diǎn)（1500）……圖4-4貯油點(diǎn)及貯油量示意綜上分析，從終點(diǎn)開始分別間隔500，500/3，500/5，500/7，……（公里）設(shè)立貯油點(diǎn)，直到總距離超過(guò)1000公里。每個(gè)貯油點(diǎn)的油量為500，1000，1500，……。算法設(shè)計(jì)：由模型知道此問題并不必用倒推算法解決（只是分析過(guò)程用的是倒推法），只需通過(guò)累加算法就能解決。變量說(shuō)明：dis表示距終點(diǎn)的距離，1000-dis則表示距起點(diǎn)的距離，k表示貯油點(diǎn)從后到前的序號(hào)。desert（）{intdis，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(dis<1000)

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

print(“storepoint”,k,”distance”,0,”oilquantity”,oil)；

}4.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的根。

【例1】迭代法求方程組根

算法說(shuō)明：方程組解的初值X=（x0，x1，…，xn-1）,迭代關(guān)系方程組為：xi=gi(X)(i=0,1,…,n-1),w為解的精度,則算法如下：

for

(i=0;i<n;i++)

x[i]=初始近似根;

do{k=k+1;for

(i=0;i<n;i

y[i]=x[i];

for

(i=0;i<n;i++)

x[i]=gi(X);

for

(i=0;i<n;i++)c=c+fabs(y[i]-x[i])；

}

while

(c>wandk<maxn)；

for

(i=0;i<n;i++)

print(i，“變量的近似根是”，x[i])；

}【例2】牛頓迭代法牛頓迭代法又稱為切線法，它比一般的迭代法有更高的收斂速度，如圖4-5所示。首先,選擇一個(gè)接近函數(shù)f(x)零點(diǎn)的x0,計(jì)算相應(yīng)的f(x0)和切線斜率f‘(x0)（這里f’表示函數(shù)f的導(dǎo)數(shù)）。然后我們計(jì)算穿過(guò)點(diǎn)(x0,f(x0))且斜率為f‘(x0)的直線方程為：和x軸的交點(diǎn)的x坐標(biāo),也就是求如下方程的解：

將新求得交點(diǎn)的x坐標(biāo)命名為x1。如圖4-5所示，通常x1會(huì)比x0更接近方程f(x)=0的解。接下來(lái)用x1開始下一輪迭代

.圖4-5牛頓迭代法

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

下面給出用牛頓迭代法，求形如ax3+bx2+cx+d=0方程根的算法，系數(shù)a、b、c、d的值依次為1、2、3、4，由主函數(shù)輸入。求x在1附近的一個(gè)實(shí)根。求出根后由主函數(shù)輸出。

main(){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);}

令[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(b0)*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)=x^3/2+2x^2-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。main(){floatx,x1=0,x2=2,f1,f2,f;print(“inputa,b(f(a)*f(b)<0)”);input(a,b);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=x1*x1*x1/2+2*x1*x1-8;}elsex2=x;}while(fabs(f)>=1e-4);print("root=",x);}4.2蠻力法4.2.1枚舉法4.2.2其它范例

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

4．2．1枚舉法

枚舉（

enumerate）法（窮舉法）是蠻力策略的一種表現(xiàn)形式，也是一種使用非常普遍的思維方法。它是根據(jù)問題中的條件將可能的情況一一列舉出來(lái)，逐一嘗試從中找出滿足問題條件的解。但有時(shí)一一列舉出的情況數(shù)目很大，如果超過(guò)了我們所能忍受的范圍，則需要進(jìn)一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數(shù)目。用枚舉法解決問題，通常可以從兩個(gè)方面進(jìn)行算法設(shè)計(jì)：

1）找出枚舉范圍：分析問題所涉及的各種情況。

2）找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達(dá)式表示。【例1】百錢百雞問題。中國(guó)古代數(shù)學(xué)家張丘建在他的《算經(jīng)》中提出了著名的“百錢百雞問題”：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何?算法設(shè)計(jì)1：通過(guò)對(duì)問題的理解，讀者可能會(huì)想到列出兩個(gè)三元一次方程，去解這個(gè)不定解方程，就能找出問題的解。這確實(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

算法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);}

}算法分析：以上算法需要枚舉嘗試20*34*100=68000次。算法的效率顯然太低算法設(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()

{

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)時(shí)約束條件又限定Z能被3整除時(shí)，才會(huì)判斷“5*x+3*y+z/3=100”。這樣省去了z不整除3時(shí)的算術(shù)計(jì)算和條件判斷，進(jìn)一步提高了算法的效率。【例2】解數(shù)字迷：ABCAB

×ADDDDDD算法設(shè)計(jì)1：按乘法枚舉1)枚舉范圍為：

A：3——9（A=1，2時(shí)積不會(huì)得到六位數(shù)）,B：0——9,C：0——9六位數(shù)表示為A*10000+B*1000+C*100+A*10+B，共嘗試800次。2)約束條件為：每次嘗試，先求六位數(shù)與A的積，再測(cè)試積的各位是否相同，若相同則找到了問題的解。測(cè)試積的各位是否相同比較簡(jiǎn)單的方法是，從低位開始，每次都取數(shù)據(jù)的個(gè)位，然后整除10，使高位的數(shù)字不斷變成個(gè)位，并逐一比較。

算法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);

}}算法說(shuō)明1：算法中對(duì)枚舉出的每一個(gè)五位數(shù)與A相乘，結(jié)果存儲(chǔ)在變量E中。然后，測(cè)試得到的六位數(shù)E是否各個(gè)位的數(shù)字都相同。鑒于要輸出結(jié)果，所以不要改變計(jì)算結(jié)果，而另設(shè)變量E1，用于測(cè)試運(yùn)算。算法分析1：以上算法的嘗試范圍是A：3——9，B：0——9，C：0——9。共嘗試800次，每次，不是一個(gè)好的算法。算法設(shè)計(jì)2：將算式變形為除法：DDDDDD/A=ABCAB。此時(shí)只需枚舉A：3——9D：1——9，共嘗試7*9=63次。每次嘗試，測(cè)試商的萬(wàn)位、十位與除數(shù)是否相同，千位與個(gè)位是否相同，都相同時(shí)為解。算法2如下:main（）{intA,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(EmodA=0)F=E\A;

if(F\10000=Aand(Fmod100)\10=A)if(F\1000==Fmod10)print(F，”*”，A，”=”，E);}}

蠻力法的表現(xiàn)形式非常多，如第三章3.2.4例題、3.2.5例1及本章下一節(jié)4.3.3例4的算法1等。本節(jié)將通過(guò)蠻力策略，用算法模擬問題中所描述的全部過(guò)程和全部狀態(tài)，來(lái)找出問題的解，并與經(jīng)過(guò)數(shù)學(xué)建模后的算法進(jìn)行效率上的比較。

4．2．2其它范例【例3】獄吏問題某國(guó)王對(duì)囚犯進(jìn)行大赦，讓一獄吏n次通過(guò)一排鎖著的n間牢房，每通過(guò)一次，按所定規(guī)則轉(zhuǎn)動(dòng)n間牢房中的某些門鎖,每轉(zhuǎn)動(dòng)一次,原來(lái)鎖著的被打開,原來(lái)打開的被鎖上；通過(guò)n次后，門鎖開著的，牢房中的犯人放出，否則犯人不得獲釋。轉(zhuǎn)動(dòng)門鎖的規(guī)則是這樣的，第一次通過(guò)牢房，要轉(zhuǎn)動(dòng)每一把門鎖，即把全部鎖打開；第二次通過(guò)牢房時(shí)，從第二間開始轉(zhuǎn)動(dòng)，每隔一間轉(zhuǎn)動(dòng)一次；第k次通過(guò)牢房，從第k間開始轉(zhuǎn)動(dòng)，每隔k-1間轉(zhuǎn)動(dòng)一次；問通過(guò)n次后，那些牢房的鎖仍然是打開的？算法設(shè)計(jì)1：1）用n個(gè)空間的一維數(shù)組a[n],每個(gè)元素記錄一個(gè)鎖的狀態(tài)，1為被鎖上，0為被打開。2）用數(shù)學(xué)運(yùn)算方便模擬開關(guān)鎖的技巧，對(duì)i號(hào)鎖的一次開關(guān)鎖可以轉(zhuǎn)化為算術(shù)運(yùn)算：a[i]=1-a[i]。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)模擬獄吏的開關(guān)鎖過(guò)程，最后當(dāng)?shù)趇號(hào)牢房對(duì)應(yīng)的數(shù)組元素a[i]為0時(shí)，該牢房的囚犯得到大赦。算法1如下：

main1(){int*a,i,j,n;input(n);a=calloc(n+1,sizeof(int));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.”);}算法分析：以一次開關(guān)鎖計(jì)算，算法的時(shí)間復(fù)雜度為n(1+1/2+1/3+……+1/n)=O(nlogn)。問題分析：轉(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ù)的牢房；……則獄吏問題是一個(gè)關(guān)于因子個(gè)數(shù)的問題。令d(n)為自然數(shù)n的因子個(gè)數(shù)，這里不計(jì)重復(fù)的因子，如4的因子為1，2，4共三個(gè)因子，而非1，2，2，4。則d(n)有的為奇數(shù)，有的為偶數(shù)，見下表:

表4-3編號(hào)與因數(shù)個(gè)數(shù)的關(guān)系

n12345678910111213141516……d(n)1223242434262445……

數(shù)學(xué)模型1：上表中的d(n)有的為奇數(shù)，有的為偶數(shù)，由于牢房的門開始是關(guān)著的，這樣編號(hào)為i的牢房，所含1——i之間的不重復(fù)因子個(gè)數(shù)為奇數(shù)時(shí)，牢房最后是打開的，反之，牢房最后是關(guān)閉的。算法設(shè)計(jì)2:

1）算法應(yīng)該是求出每個(gè)牢房編號(hào)的不重復(fù)的因子個(gè)數(shù)，當(dāng)它為奇數(shù)時(shí)，這里邊的囚犯得到大赦。2）一個(gè)數(shù)的因子是沒有規(guī)律的，只能從1——n枚舉嘗試。算法2如下：main2(){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.”);}}算法分析：獄吏開關(guān)鎖的主要操作是a[i]=1-a[i];共執(zhí)行了n*(1+1/2+1/3+……+1/n)次，時(shí)間近似為復(fù)雜度為O（nlogn）。使用了n個(gè)空間的一維數(shù)組。算法2沒有使用輔助空間，但由于求一個(gè)編號(hào)的因子個(gè)數(shù)也很復(fù)雜，其主要操作是判斷imodj是否為0，共執(zhí)行了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且a≠b時(shí)，必有兩個(gè)因子a，b;只有n為完全平方數(shù)，也即當(dāng)n=a2時(shí),才會(huì)出現(xiàn)d(n)為奇數(shù)的情形。算法設(shè)計(jì)3：這時(shí)只需要找出小于n的平方數(shù)即可。算法3如下：main3(){ints,i,j,n;input(n);for(i=1;i<=n;i++)if（i*i<=n）print(i,”isfree.”);elsebreak;}

由此算法我們應(yīng)當(dāng)注意：在對(duì)運(yùn)行效率要求較高的大規(guī)模的數(shù)據(jù)處理問題時(shí)，必須多動(dòng)腦筋找出效率較高的數(shù)學(xué)模型及其對(duì)應(yīng)的算法。4.3分而治之算法4.3.1分治算法框架4.3.2二分法4.3.3二分法變異4.3.4其它分治方法4．3．1分治算法框架

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

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

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

2．適合用分治法策略的問題當(dāng)求解一個(gè)輸入規(guī)模為n且取值又相當(dāng)大的問題時(shí)，用蠻力策略效率一般得不到保證。若問題能滿足以下幾個(gè)條件，就能用分治法來(lái)提高解決問題的效率。1）

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

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

分治法的一般的算法設(shè)計(jì)模式如下：Divide-and-Conquer(intn)/n為問題規(guī)模/{if（n≤n0）/n0為可解子問題的規(guī)模/

{解子問題；

return(子問題的解)；}for（i=1;i<=k;i++）/分解為較小子問題p1,p2,……pk/

yi=Divide-and-Conquer(|Pi|);/遞歸解決Pi/

T=MERGE(y1,y2,...,yk);/合并子問題/return(T);}

其中|P|表示問題P的規(guī)模；n0為一閾值，表示當(dāng)問題P的規(guī)模不超過(guò)n0時(shí)，問題已容易直接解出，不必再繼續(xù)分解。算法MERGE(y1,y2,...,yk)是該分治法中的合并子算法，用于將P的子問題P1,P2,...,Pk的相應(yīng)的解y1,y2,...,yk合并為P的解。在一些問題中不需要這一步。如析半查找、4．3．2中的例1、例2等。4．3．2二分法

不同于現(xiàn)實(shí)中對(duì)問題（或工作）的分解，可能會(huì)考慮問題（或工作）的重點(diǎn)、難點(diǎn)、承擔(dān)人員的能力等來(lái)進(jìn)行問題的分解和分配。在算法設(shè)計(jì)中每次一個(gè)問題分解成的子問題個(gè)數(shù)一般是固定的，每個(gè)子問題的規(guī)模也是平均分配的。當(dāng)每次都將問題分解為原問題規(guī)模的一半時(shí)，稱為二分法。二分法是分治法較常用的分解策略，數(shù)據(jù)結(jié)構(gòu)課程中的折半查找、歸并排序等算法都是采用此策略實(shí)現(xiàn)的?！纠?】金塊問題：老板有一袋金塊(共n塊)，最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。算法設(shè)計(jì)1：比較簡(jiǎn)單的方法是逐個(gè)的進(jìn)行比較查找。先拿兩塊比較重量，留下重的一個(gè)與下一塊比較，直到全部比較完畢，就找到了最重的金子。算法類似于一趟選擇排序，算法如下：

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

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

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

}算法分析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(n—1)/2。

算法設(shè)計(jì)2:問題可以簡(jiǎn)化為：在含n（n是2的冪（n>=2））個(gè)元素的集合中尋找極大元和極小元。用分治法（二分法）可以用較少比較次數(shù)地解決上述問題：1）

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

遞歸分解直到每組元素的個(gè)數(shù)≤2，可簡(jiǎn)單地找到最大（?。┲怠?）

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

算法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;

}

算法分析：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)的?！纠?】殘缺棋盤殘缺棋盤是一個(gè)有2k×2k

（k≥1）個(gè)方格的棋盤，其中恰有一個(gè)方格殘缺。圖4-7給出k=1時(shí)各種可能的殘缺棋盤，其中殘缺的方格用陰影表示。

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

-1)/3。

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

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

圖4-9其它4*4的殘缺棋盤2）棋盤的識(shí)別棋盤的規(guī)模是一個(gè)必要的信息，有了這個(gè)信息，只要知道其左上角的左上角方格所在行、列就可以唯一確定一個(gè)棋盤了，殘缺方格或“偽”殘缺方格直接用行、列號(hào)記錄。?

tr棋盤中左上角方格所在行。?

tc棋盤中左上角方格所在列。?

dr殘缺方塊所在行。?dl殘缺方塊所在列。?size棋盤的行數(shù)或列數(shù)。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：用二維數(shù)組board[][]，模擬棋盤。覆蓋殘缺棋盤所需要的三格板數(shù)目為：(size2-1)/3將這些三格板編號(hào)為1到(size2-1)/3。則將殘缺棋盤三格板編號(hào)的存儲(chǔ)在數(shù)組board[][]的對(duì)應(yīng)位置中，這樣輸出數(shù)組內(nèi)容就是問題的解。結(jié)合圖4-9，理解算法。算法如下：

intamount=0;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);}圖4-9

一個(gè)4*4的殘缺棋盤及其解

Cover(inttr,inttc,intdr,intdc,intsize){if(size<2)return;intt=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;

//覆蓋１號(hào)三格板

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);

｝elseif(dr<tr+s&&dc>=tc+s)//殘缺方格位于右上象限｛Cover(tr,tc+s,dr,dc,s);

Board[tr+s-1][tc+s-1]=t;//覆蓋２號(hào)三格板

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;

//覆蓋３號(hào)三格板

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);｝elseif(dr>=tr+s&&dc>=tc+s)

//殘缺方格位于右下象限｛Cover(tr+s,tc+s,dr,dc,s);

Board[tr+s-1][tc+s-1]=t;

//覆蓋４號(hào)三格板

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個(gè)三格板，所以算法的時(shí)間復(fù)雜性為Ｏ（size2）。

4．3．3二分法變異

【例３】求最長(zhǎng)連續(xù)不升數(shù)列有一組數(shù)據(jù)找出其中最長(zhǎng)的連續(xù)不升數(shù)列算法設(shè)計(jì)：此問題用二分法分解后的兩個(gè)子序列（子問題）并不獨(dú)立，因?yàn)橛锌赡茏铋L(zhǎng)的連續(xù)不升數(shù)列正好存在于兩個(gè)子序列的連接位置。如果將所給的序列a[1..n]分為長(zhǎng)度相等的2段

a[1——(n/2)]和a[(n/2)+1——n],則a[1.n]的最長(zhǎng)連續(xù)不升數(shù)列有3種情況：

問題分析：若用二分法將實(shí)例中的數(shù)據(jù)分解為兩組(-2,11,-4),（13,-5,-2），第一個(gè)子問題的解是11，第二個(gè)子問題的解是13，兩個(gè)子問題的解不能簡(jiǎn)單地得到原問題的解。由此看出這個(gè)問題不能分解用二分法成解為獨(dú)立的兩個(gè)子問題，子問題中間還有公共的子問題，這類問題稱為子問題重疊類的問題。那么，怎樣解決這類問題呢？雖沒有通用的方法，但本章4.5節(jié)的介紹的動(dòng)態(tài)規(guī)劃算法是一種較好的解決方法。下面我們?nèi)杂枚址ń鉀Q這類問題中的一些簡(jiǎn)單問題，學(xué)習(xí)一下如何處理不獨(dú)立的子問題。算法設(shè)計(jì)：分解方法和上面的例題一樣采用二分法，雖然分解后的子問題并不獨(dú)立，但通過(guò)對(duì)重疊的子問題進(jìn)行專門處理，并對(duì)所有子問題合并進(jìn)行設(shè)計(jì)，就可以用二分策略解決此題。

如果將所給的序列a[1..n]分為長(zhǎng)度相等的2段a[1——(n/2)]和a[(n/2)+1——n],分別求出這2段的最大子段和,則a[1.n]的最大子段和有3種情形。1）a[1..n]的最長(zhǎng)連續(xù)不升數(shù)列與a[1..(n/2)]的最長(zhǎng)連續(xù)不升數(shù)列相同;2)a[1..n]的最長(zhǎng)連續(xù)不升數(shù)列與a[(n/2)+1..n]的最長(zhǎng)連續(xù)不升數(shù)列相同;3)a[1..n]的最長(zhǎng)連續(xù)不升數(shù)列為∑a[k],且

1≤i≤(n/2),(n/2),(n/2)+1≤j≤n。情況1）和情況2）可分別遞歸求得。對(duì)于情況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)時(shí)的最優(yōu)值。算法如下：intmax_sum3(inta[],intn){return(max_sub_sum(a,1,n));}max_sub_sum(inta[],intleft,intright){intcenter,i,j,sum,left_sum,right_sum,s1,s2,lefts,rights;if(left=right)

if(a[left]>0)return(a[left]);

elsereturn(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;/處理情形3/lefts=0;for(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<left_sumandright_sum<left_sum)rturn(left_sum);if(s1+s2<right_sum)return(right_sum);return(s1+s2);}}【例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ù)的乘法運(yùn)算。數(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)。

算法設(shè)計(jì)1：存儲(chǔ)好兩個(gè)高精度數(shù)據(jù)后，我們模擬豎式乘法，讓兩個(gè)高精度數(shù)據(jù)的按位交叉相乘，并逐步累加，即可得到精確的計(jì)算結(jié)果。用二重循環(huán)就可控制兩個(gè)數(shù)不同位相乘的過(guò)程。只考慮正整數(shù)的乘法，算法細(xì)節(jié)設(shè)計(jì)如下：1)對(duì)于大整數(shù)比較方便的輸入方法是，按字符型處理，存儲(chǔ)在字符串?dāng)?shù)組s1、s2中，計(jì)算結(jié)果存儲(chǔ)在整型數(shù)組a中。2)通過(guò)字符的ASCII碼，數(shù)字字符可以直接參與運(yùn)算，k位數(shù)字與j位數(shù)字相乘的表達(dá)式為：s1[k]-48)*(s2[j]-48)。這是C語(yǔ)言的處理方法，其它程序設(shè)計(jì)語(yǔ)言有對(duì)應(yīng)的函可以實(shí)現(xiàn)數(shù)字字符與數(shù)字的轉(zhuǎn)換，這里不詳細(xì)介紹了。3)每一次數(shù)字相乘的結(jié)果位數(shù)是不固定的，而結(jié)果數(shù)組中每個(gè)元素只存儲(chǔ)一位數(shù)字，所以用變量b暫存結(jié)果，若超過(guò)1位數(shù)則進(jìn)位，用變量d存儲(chǔ)。這樣每次計(jì)算的表達(dá)式為：

b=a[i]+(s1[k]-48)*(s2[j]-48)+d;。main(){longb,c,d;inti,i1,i2,j,k,n,n1,n2,a[256];

chars1[256],s2[256];

input(s1);input(s2);for(i=0;i<255;i++)a[i]=0;n1=strlen(s1);n2=strlen(s2);d=0;for(i1=0,k=n1-1;i1<n1;i1++,k--){for(i2=0,j=n2-1;i2<n2;i2++,j--){i=i1+i2;b=a[i]+(s1[k]-48)*(s2[j]-48)+d;a[i]=bmod10;d=b/10;}

while(d>0){i=i+1;a[i]=a[i]+dmod10;d=d/10;}n=i;}for(i=n;i>=0;i--)print(a[i]);}算法說(shuō)明：循環(huán)變量j、k分別是兩個(gè)乘數(shù)字符串的下標(biāo)。i1表示字符串str1由低位到高位的位數(shù)，范圍0——n1-1（與k相同）。i2表示字符串str2由低位到高位的位數(shù)，范圍0——n2-1（與j相同）。i表示乘法正在運(yùn)算的位，也是計(jì)算結(jié)果存儲(chǔ)的位置。算法分析1：算法是以n1,n2代表兩個(gè)乘數(shù)的位數(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的分段

將n位的二進(jìn)制整數(shù)X和Y各分為2段，每段的長(zhǎng)為n/2位(為簡(jiǎn)單起見，假設(shè)n是2的冪)，如圖4-10所示。顯然問題的答案并不是A*C*K1+C*D*K2（K1、K2與A、B、C、D無(wú)關(guān)），也就是說(shuō)，這樣做并沒有將問題分解成兩個(gè)獨(dú)立的子問題。按照乘法分配律，分解后的計(jì)算過(guò)程如下：記：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)式：

T（1）=1T（n）=4T(n/2)+O(n)（2）

由此遞歸式迭代過(guò)程如下：T(n)=4T(n/2)+cn=4(4T(n/4)+cn/2)+cn=16(T(n/8)+cn/4)+3cn/2+cn=……

=

+4k-1*2c+4k-2*4c+……+4c2k-1+c2k

=O（4k）=O(nlog4)

=O（n2）所以可得算法的時(shí)間復(fù)雜度為T(n)=O(n2)。模型改進(jìn)：可以把X*Y寫成另一種形式：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)

用解遞歸方程的迭代公式法，不妨設(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)。MULT(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=1andY=1)return(S)；

elsereturn(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);}

}4．3．4其它分治方法

以上的例子都是用二分策略把問題分解為與原問題相似“相等”的子問題。下面看幾個(gè)用“非等分二分法”解決問題的例子。選擇問題就是“從一組數(shù)中選擇的第k小的數(shù)據(jù)”，這個(gè)問題的一個(gè)應(yīng)用就是尋找中值元素，此時(shí)k=[n/2]。中值是一個(gè)很有用的統(tǒng)計(jì)量，例如中間工資，中間年齡，中間重量等。k取其他值也是有意義的，例如，通過(guò)尋找第k=n/2、k=n/3和k=n/4的年齡,可將人口進(jìn)行劃分，了解人口的分布情況。這個(gè)問題可以通過(guò)排序來(lái)解決，但根據(jù)《數(shù)據(jù)結(jié)構(gòu)》課程的經(jīng)驗(yàn)，最好的排序算法的復(fù)雜性也是O（n*log(n)），下面我們要利用分治法，找到復(fù)