1、分治策略（3）【例31 一元三次方程求解有形如：ax3 +bx2+cx+d = 0這樣的一個一元三次方程。給出該方程中各項的系數（a, b, c,d均為實數），并約定該方程存在三個不同實根（根的范圍在-100至100之間），且根與根之差的絕對值R 1。要求由小到大依次在同一行輸出這三個實根（根與根之間留有空格），并精確到小數點后 2位。提示：記方程 f （x） =0,若存在 2個數x1和x2,且x1<x2 , f （x1） *f （x2） < 0, 則在（x1 , x2）之間一定有一個根。輸入：a, b, c, d輸出：三個實根（根與根之間留有空格） 輸入輸出樣例輸入：1-5-4

2、20輸出：-2.00 2.00 5.00【算法分析】這是一道有趣的解方程題。為了便于求解，將原方程f（x）= ax +bx +cx+d = 0變換成f' （x）=3x+b' x+c' x+d' =0的形式（其中），f（x）和f' （x）的根不變。設x的值域（-100至100之間）中有 x,其左右兩邊相距0.0005的地方有x1和x2兩個數，即x1=x-0.0005 , x2=x+0.0005 , x1和x2間的距離（0.001）滿足精度要求（精確到小數點后 2位）。若出現如圖 1所示的兩種情況之一，則確定 x為f' （x）=0的根。有兩種方法計算

3、f' （x）=0的根x:1 .枚舉法根據根的值域和根與根之間的間距要求(A1),我們不妨將根的值域擴大100倍(-10000WxW 10000),依次枚舉該區間的每一個整數值X,并在題目要求的精度內設定區間：若區間端點的函數值f' (x1)和f' (x2)異號或者在區間端點x1的函數值f' (x1)=0 ,則確定為f' (x)=0的一個根。由此得出算法：2 .分治法枚舉根的值域中的每一個整數x(-100wxw 100)。由于根與根之差的絕對值R1,因此設定搜索區間x1 , x2,其中 x1=x, x2=x+1。若f' (x1)=0,則確定x1為f

4、' (x)的根；f' (x1)*f ' (x2)>0 ,則確定根x不在區間x1 , x2內，設定x2, x2+1為下一個搜索區間f' (x1)*f ' (x2)<0 ,則確定根 x在區間x1 , x2內。如果確定根 x在區間x1 , x2內的話(f' (x1)*f ' (x2)<0 ),如何在該區間找到根的確切位置。采用二分法，將區間x1, x2分成左右兩個子區間：左子區間x1, x和右子區間x, x2(其中)：如果f' (x1)*f ' (x) w 0,則確定根在左區間x1 , x內，將x設為該區間的右

5、指針(x2=x), 繼續對左區間進行對分；如果 f' (x1)*f ' (x)>0 ,則確定根在右區間x, x2內，將x設為 該區間的左指針(x1=x),繼續對右區間進行對分；上述對分過程一直進行到區間的間距滿足精度要求為止(x2-x1<0.001 )。此時確定 x1為f' (x)的根。由此得出算法：其中f(x)的函數說明如枚舉法所示。【例4】小車問題(car)【問題描述】甲、乙兩人同時從 A地出發要盡快同時趕到 B地。出發時 A地有一輛小車，可是這輛小 車除了駕駛員外只能帶一人。已知甲、乙兩人的步行速度一樣，且小于車的速度。問：怎樣 利用小車才能使兩人盡快

6、同時到達。【問題輸入】僅一行，三個數據分別表示AB兩地的距離s,人的步行速度a,車的速度bo【問題輸出】兩人同時到達 B地需要的最短時間。【輸入輸出樣例】 car.in 120 5 25car.out9.6000000000E+00【算法分析】最佳方案為：甲先乘車到達K處后下車步行，小車再回頭接已走到 C處的 乙，在D處相遇后，乙再乘車趕往 B,最后甲、乙一起到達 B地。如下圖所示，這時所用的 時間最短。這樣問題就轉換成了求 K處的位置，我們用二分法，不斷嘗試，直到滿足同時到達的時間精度。算法框架如下：1、輸入 s, a, b;2、c0:=0 ; c1:=s ; c:=(c0+c1)/2 ;3

7、、求 t1 , t2 ;4、如果 t1<t2 ,那么 c:=(c0+c)/2 否貝U c:=(c+c1)/2;反復執行3和4,直到abs(t1-t2)滿足精度要求(即小于誤差標準)。參考程序(略)【例51循環比賽日程表(match.?)設有n個選手的循環比賽， 其中n=2m,要求每名選手要與其他 n-1名選手都賽一次。 每 名選手每天比賽一次，循環賽共進行n-1天。要求每天沒有選手輪空.以下是八名選手時的循環比賽表，表中第一行為八位選手的編號，下面七行依次是每位選手每天的對手。12345678214365873412785643218765567812346587214378563412

8、87654321問題分析從八位選手的循環比賽表中可以看出，這是一個具有對稱性的方陣，可以把方陣一分為四來看，那么左上角的4*4的方陣就是前四位選手的循環比賽表，而右上角的4*4的方陣就是后四位選手的循環比賽表，它們在本質上是一樣的，都是4個選手的循環比賽表，所不同的只 是選手編號不同而已，將左上角中方陣的所有元素加上4就能得到右上角的方陣.下方的兩個方陣表示前四位選手和后四位選手進行交叉循環比賽的情況，同樣具有對稱性，將右上角方陣復制到左下角即得到 1,2,3,4四位選手和5,6,7,8四位選手的循環比賽表，根據對稱性， 右下角的方陣應與左上角的方陣相同.這樣，八名選手的循環比賽表可以由四名選

9、手的循環比賽表根據對稱性生成出來 .同樣地，四名選手的循環比賽表可以由二名選手的循環比賽表 根據對稱性生成出來，而兩名選手的循環比賽表可以說是已知的，這種程序設計方法叫做分治法，其基本思想是把一個規模為n的問題分成若干個規模較小的問題，使得從這些較小問題的解易于構造出整個問題的解.程序中用數組matchlist記錄n名選手的循環比賽表,整個循環比賽表從最初的1*1的方陣按上述規則生成出2*2的方陣，再生成出4*4的方陣，直到生成出整個循環比賽表為止.變量half表示當前方陣的大小，也是要生成的下一個方陣的大小的一半.參考程序const maxn=32;maxm=5;var i,j,k,m,n,

10、half:integer;matchlist:array 1.maxn,1.maxn of integer;beginwrite('Input m:'); readln(m);n:=1; for i:=1 to m do n:=n*2;k:=1; matchlist1,1:=1; half:=1;while k<=m dobeginfor i:=1 to half do構造右上角方陣for j:=1 to half do matchlisti,j+half:=matchlisti,j+half;for i:=1 to half do對稱交換構造下半部分方陣for j:=1

11、 to half do beginmatchlisti+half,j:=matchlisti,j+half;matchlisti+half,j+half:=matchlisti,j end;half:=half*2; k:=k+1end;for i:=1 to n dobeginfor j:=1 to n do write(matchlisti,j:4); writelnend;end.樣例Input m: 4 _Output:1 23456789 101112131415162 14365871091211141316153 41278561112910151613144 321876512

12、11109161514135 67812341314151691011126 58721431413161510912117 85634121516131411129108 765432116151413121110 99 101112 13 1415161234 5 6 7 810 91211141316152143658711 12910151613143412785612 11109161514134321876513 14151691011125678123414 131615109 12 116587214315 1613141112 9 107856341216 151413121

13、1 10 987654321【例6】殘缺棋盤問置【問題描述】殘缺棋盤是一個2kx 2k個方格的棋盤.其中恰好有一個方格殘缺，現在要求三格板覆蓋棋 盤，在此覆蓋中兩塊三格板不能重疊，三格板也不能覆蓋在殘缺的方格上。當k=l時各種可能的的殘缺的棋盤如圖4-3所示，其中殘缺部分用陰影表示。三格板的四個不同方向如下圖 4 4所示:輸入：第一行輸入棋盤總行敷.第二行輸入殘缺的格子坐標。輸出：覆蓋的矩陣圖【樣例輸入】441【樣例輸出】2233211344150455【問題分析】：很明顯，當K=0時是不需要三格板的，而當K=1時只需要1塊三格扳就夠了。那么關鍵在于K>1時情況就有些復雜了，以 K= 2

14、時的某種情況（如圖45所示）為例，如果我們按一般的 搜索來實現也是可行的，但在時問上會有很多浪費。不妨先歸納一下放三格板時是否有規律 可循：如果將第一塊三格板放在如圖4-5所示的位置上時，讓區域居中的原來無陰影的小區域都變成有一個陰影，這樣四個相等小區域都缺了一角，問題一下子明朗了。在本例中需要的數據有：(1) 用一個二維數組 boardi,j表示棋盤，其中i表示棋盤的行，j表示棋盤的列;(2) 一個表示三格板數目的全局變量title,該變量同時也用來表示每次覆蓋的三格板的編號。遞歸中所使用的函數為： fugai(tr,tc,dr,dc,size)tr整型，表示區域左上角的行號；tc整型，表示

15、區域左上角的列號；dr整型，表示殘缺格所在的行號；dc 整型，表示殘缺格所在的列號：size 整型，表示待放置區域的總行數或總列數。【算法描述】function fugai(tr,tc,dr,dc,size:integer);if size=1 then 結束；title:=title+1; 三格板的數目 +1size:=size div 2; 區域大小減半if殘缺格在下部then if殘缺格在右部then begin 將右下角設為陰影，填上三格板編號；分別對四個小區域進行覆蓋endelse begin 將左下角設為陰影，填上三格板編號：分別對四個小區域進行覆蓋endelse if殘缺格在右部

16、then begin 將右上角設為陰影，填上三格板編號；分別對四個小區域進行覆蓋endelse begin將左上角設為陰影，填上三格板編號；分別對四個小區域進行覆蓋end【參考程序】：program p4_2(input,output);var n,x,y,title:integer;board:array 1.100,1.100 of integer;procedure fugai(tr,tc,dr,dc,size:integer);var xr,xc,yr,yc:integer;beginif size=1then exitelse title:=title+1;size:=size di

17、v 2;if dr>=tr+size thenbeginif dc>=tc+sizethenbeginboardtr+size-1,tc+size-1:=title;boardtr+size-1,tc+size:=title;boardtr+size,tc+size-1:=title;fugai(tr,tc,tr+size-1,tc+size-1,size);fugai(tr+size,tc,tr+size,tc+size-1,size);fugai(tr,tc+size,tr+size-1,tc+size,size); fugai(tr+size,tc+size,dr,dc,si

18、ze);endelsebeginboardtr+size-1,tc+size-1:=title;boardtr+size-1,tc+size:=title;boardtr+size,tc+size:=title;fugai(tr,tc,tr+size-1,tc+size-1,size);fugai(tr+size,tc,dr,dc,size);fugai(tr,tc+size,tr+size-1,tc+size,size);fugai(tr+size,tc+size,tr+size,tc+size,size);endendelsebeginif dc>=tc+sizethenbeginb

19、oardtr+size-1,tc+size-1:=title;boardtr+size,tc+size-1:=title;boardtr+size,tc+size:=title;fugai(tr,tc,tr+size-1,tc+size-1,size);fugai(tr+size,tc,tr+size,tc+size-1,size);fugai(tr,tc+size,dr,dc,size);fugai(tr+size,tc+size,tr+size,tc+size,size);endelsebeginboardtr+size-1,tc+size:=title;boardtr+size,tc+s

20、ize-1:=title;boardtr+size,tc+size:=title;fugai(tr,tc,dr,dc,size);fugai(tr+size,tc,tr+size,tc+size-1,size);fugai(tr,tc+size,tr+size-1,tc+size,size);fugai(tr+size,tc+size,tr+size,tc+size,size);endend;end;procedure print(n:integer);var i,j:integer;beginfor i:=1 to n dobeginfor j:=1 to n do write(boardi,j:5);writelnend;end;beginassign(input,'word.in');reset(input);assign(output,'word.out');rewrite(output);readln(n);readln(x,y);fugai(1,1,x,y,n);print(n);end.上機練習題：1、一元三次方程求解(e