第7章分治算法

1、第七章第七章 分治算法分治算法 所謂分治就是指的分而治之，即將較大規(guī)模的問題分解成幾個(gè)較小規(guī)模的問題，通過對(duì)較小規(guī)模問題的求解達(dá)到對(duì)整個(gè)問題的求解。當(dāng)我們將問題分解成兩個(gè)較小問題求解時(shí)的分治方法稱之為二分法。分治的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。找出各部分的解，然后把各部分的解組合成整個(gè)問題的解。 1、解決算法實(shí)現(xiàn)的同時(shí)，需要估算算法實(shí)現(xiàn)所需時(shí)間。分治算法時(shí)間是這樣確定的： 解決子問題所需的工作總量（由子問題的個(gè)數(shù)、解決每個(gè)子問題的工作量 決定）合并所有子問題所需的工作量。2、分治法是把任意大小問題盡可能地等分成兩個(gè)子問題的遞歸算法。

2、 3、分治的具體過程（以二分法為例）： begin 開始 if 問題不可分 then 返回問題解 else begin 從原問題中劃出含一半運(yùn)算對(duì)象的子問題1； 遞歸調(diào)用分治法過程，求出解1； 從原問題中劃出含另一半運(yùn)算對(duì)象的子問題2； 遞歸調(diào)用分治法過程，求出解2； 將解1、解2組合成整個(gè)問題的解；end; end; /結(jié)束【例【例1】快速排序快速排序(遞歸算法遞歸算法)procedure qsort(l,r:integer);var i,j,mid,p:integer;begin i:=l; j:=r; mid:=a(l+r) div 2; /將當(dāng)前序列在中間位置的數(shù)定義為中間數(shù) repe

3、at while aimid do dec(j); /在右半部分尋找比中間數(shù)小的數(shù) if ij; if lj then qsort(l,j); /若未到兩個(gè)數(shù)的邊界，則遞歸搜索左右區(qū)間 if iy then writeln(no find) /找不到該數(shù)找不到該數(shù) else begin if akm then jc(x,k-1); /在前半中查找在前半中查找 end;end;begin readln(n); x:=1;y:=n; for i:=1to n do readln(ai); /輸入排序好的數(shù)輸入排序好的數(shù) readln(m); /輸入要查找的數(shù)輸入要查找的數(shù) jc(x,y); /遞歸

4、過程遞歸過程 readln;end.【例【例3】一元三次方程求解一元三次方程求解 有形如：ax3+bx2+cx+d0這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)（a,b,c,d均為實(shí)數(shù)），并約定該方程存在三個(gè)不同實(shí)根（根的范圍在-100至100之間），且根與根之差的絕對(duì)值1。 要求由小到大依次在同一行輸出這三個(gè)實(shí)根（根與根之間留有空格），并精確到小數(shù)點(diǎn)后2位。 提示：記方程f（x）=0，若存在2個(gè)數(shù)x1和x2，且x1x2，f（x1）*f（x2）0，則在（x1，x2）之間一定有一個(gè)根。 輸入：a，b，c，d 輸出：三個(gè)實(shí)根（根與根之間留有空格）【輸入輸出樣例】【輸入輸出樣例】輸入：1 -5 -

5、4 20 輸出：-2.00 2.00 5.00【算法分析】【算法分析】 這是一道有趣的解方程題。為了便于求解，設(shè)方程f(x)=ax3+bx2+cx+d0，設(shè)x的值域（-100至100之間）中有x， 其左右兩邊相距0.0005的地方有x1和x2兩個(gè)數(shù)，即 x1=x-0.0005，x2=x+0.0005。x1和x2間的距離（0.001）滿足精度要求（精確到小數(shù)點(diǎn)后2位）。若出現(xiàn)如圖1所示的兩種情況之一，則確定x為f(x)=0的根。有兩種方法計(jì)算f(x)=0的根x:1枚舉法枚舉法 根據(jù)根的值域和根與根之間的間距要求(1)，我們不妨將根的值域擴(kuò)大100倍(-10000 x10000)，依次枚舉該區(qū)間的

6、每一個(gè)整數(shù)值x，并在題目要求的精度內(nèi)設(shè)定區(qū)間：x1=，x2=。若區(qū)間端點(diǎn)的函數(shù)值f(x1)和f(x2)異號(hào)或者在區(qū)間端點(diǎn)x1的函數(shù)值f(x1)=0，則確定為f(x)=0的一個(gè)根。由此得出算法： 輸入方程中各項(xiàng)的系數(shù)a，b，c，d ； for x-10000 to 10000 do /枚舉當(dāng)前根*100的可能范圍 begin x1(x-0.05)/100；x2(x+0.05)/100；/在題目要求的精度內(nèi)設(shè)定區(qū)間 if (f(x1)*f(x2)0，則確定根x不在區(qū)間x1，x2內(nèi)，設(shè)定x2，x2+1為下一個(gè)搜索區(qū)間 f(x1)*f(x2)0，則確定根x在區(qū)間x1，x2內(nèi)。 如果確定根x在區(qū)間x1，

7、x2內(nèi)的話（f(x1)*f(x2)0，則確定根在右區(qū)間x，x2內(nèi)，將x設(shè)為該區(qū)間的左指針（x1=x），繼續(xù)對(duì)右區(qū)間進(jìn)行對(duì)分； 上述對(duì)分過程一直進(jìn)行到區(qū)間的間距滿足精度要求為止（x2-x10.001）。此時(shí)確定x1為f(x)的根。由此得出算法：輸入方程中各項(xiàng)的系數(shù)a，b，c，d ；for x-100 to 100 do /枚舉每一個(gè)可能的根 begin x1x；x2x+1； /確定根的可能區(qū)間 if f(x1)=0 then write(x1:0:2， ) /若x1為根，則輸出 else if (f(x1)*f(x2)=0.001 do /若區(qū)間x1，x2不滿足精度要求，則循環(huán) begin xx

8、(x2+x1)/2； /計(jì)算區(qū)間x1，x2的中間位置 if f(x1)*f(xx)=0 then x2xx /若根在左區(qū)間，則調(diào)整右指針 else x1xx； /若根在右區(qū)間，則調(diào)整左指針 end；/while write(x1:0:2， )； /區(qū)間x1，x2滿足精度要求，確定x1為根 end； /then end； /for其中f(x)的函數(shù)說明如枚舉法所示?！纠纠?】小車問題（小車問題（car）【問題描述】【問題描述】 甲、乙兩人同時(shí)從A地出發(fā)要盡快同時(shí)趕到B地。出發(fā)時(shí)A地有一輛小車，可是這輛小車除了駕駛員外只能帶一人。已知甲、乙兩人的步行速度一樣，且小于車的速度。問：怎樣利用小車才能

9、使兩人盡快同時(shí)到達(dá)?！据斎敫袷健俊据斎敫袷健?僅一行，三個(gè)數(shù)據(jù)分別表示AB兩地的距離s，人的步行速度a，車的速度b。【輸出格式】【輸出格式】 兩人同時(shí)到達(dá)B地需要的最短時(shí)間?！据斎霕永俊据斎霕永縞ar.in120 5 25【輸出樣例】【輸出樣例】car.out9.6000000000E+00【算法分析】【算法分析】 最佳方案為：甲先乘車到達(dá)K處后下車步行，小車再回頭接已走到C處的乙，在D處相遇后，乙再乘車趕往B，最后甲、乙一起到達(dá)B地。如下圖所示，這時(shí)所用的時(shí)間最短。這樣問題就轉(zhuǎn)換成了求K處的位置，我們用二分法，不斷嘗試，直到滿足同時(shí)到達(dá)的時(shí)間精度。算法框架如下： 1、輸入s，a，b； 2

10、、c0:=0；c1:=s；c:=(c0+c1)/2； 3、求t1，t2； 4、如果t1t2，那么c:=(c0+c)/2 否則 c:=(c+c1)/2；反復(fù)執(zhí)行3和4，直到abs(t1-t2)滿足精度要求（即小于誤差標(biāo)準(zhǔn)）?！緟⒖汲绦颉俊緟⒖汲绦颉縫rogram car1(input,output);const zero=1e-4;var s,a,b,c,c0,c1,t1,t2,t3,t4:real;BEGIN assign(input,car.in); reset(input); assign(output,car.out); rewrite(output); readln(s,a,b); c

11、0:=0; c1:=s; repeat c:=(c0+c1)/2; t3:=c/b; t1:=t3+(s-c)/a; t4:=(c-t3*a)/(a+b); t2:=t3+t4+(s-(t3+t4)*a)/b; if t1t2 then c1:=c else c0:=c; until abs(t1-t2)2)個(gè)數(shù)據(jù)先分成兩組，分別求最大值、最小值，然后分別將兩組的最大值和最小值進(jìn)行比較，求出全部元素的最大值和最小值。若分組后元素還大于2，則再次分組，直至組內(nèi)元素小于等于2。 策略二：如果N等于1時(shí)，MAX=MIN=A1，如果N=2時(shí)，MAX=A1，MIN=A2或MAX=A2，MIN=A1，這是

12、非常簡(jiǎn)單的，所以此題可把所有的數(shù)作為一個(gè)序列，每次從中取出開頭兩個(gè)數(shù)，求共MAX，MIN，然后再從剩余的數(shù)中取開頭兩個(gè)數(shù)，求其MAX、MIN后與前一次的MAX、MIN比較，可得出新的MAX、MIN，這樣重復(fù)下去，直到把所有的數(shù)取完（注意最后一次取可能是只有一個(gè)數(shù)），MAX，MIN也就得到了。這就是典型的分治策略。注意：這樣做與把所有數(shù)字排序后再取MAX、MIN要快得多。3、方程、方程f(x)的根的根【問題描述】【問題描述】 求方程f(x)=2x+3x-4x=0在1，2內(nèi)的根。 提示：2x可以表示成exp(x*ln(2)的形式?！据斎敫袷健?輸入：1，2的區(qū)間值?！据敵龈袷健?輸出：方程f(x)

13、=0的根，x的值精確小數(shù)點(diǎn)10位?！据斎霕永?1 2【輸出樣例】 1.50711059574、求一元三次方程的解、求一元三次方程的解【問題描述】【問題描述】 有形如： ax3+bx2+cx+d=0一元三次方程。給出該方程中各項(xiàng)的系數(shù) (a， b， c， d 均為實(shí)數(shù) )，并約定該方程存在三個(gè)不同實(shí)根 (根的范圍在 -100至 100之間 )，且根與根之差的絕對(duì)值 =1。要求由小到大依次在同一行上輸出這三個(gè)實(shí)根。 【輸入格式】【輸入格式】 輸入：a，b，c，d【輸出格式】【輸出格式】 輸出： 三個(gè)實(shí)根（根與根之間留有空格）【輸入樣例】【輸入樣例】Equ.in1 5 4 20【輸出樣例】【輸出樣例】Equ.out-2.00 2.00 5.005、求逆序?qū)?、求逆序?qū)?給定一個(gè)序列a1,a2,an，如果存在iaj，那么我們稱之為逆序?qū)Γ竽嫘驅(qū)Φ臄?shù)目?！据斎敫袷健?第一行為n,表示序列長(zhǎng)度，接下來的n行，第i+1行表示序列中的第i個(gè)數(shù)?！据敵龈袷健?所有逆序?qū)倲?shù)?！据斎霕永縟eseq. in43232【輸出樣例】deseq.out3【數(shù)據(jù)范圍】N=105，Ai=105。6、小車問題（、小車問題（car）【問題描述】【問題描述】 甲、乙兩人同時(shí)從A地出發(fā)要盡快