分治算法策略

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