分治算法策略(3).doc

分治策略(3)【例3】一元三次方程求解有形如：ax3+bx2+cx+d＝0这样的一个一元三次方程。给出该方程中各项的系数（a，b，c，d均为实数），并约定该方程存在三个不同实根（根的范围在-100至100之间），且根与根之差的绝对值≥1。要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后2位。提示：记方程f（x）=0，若存在2个数x1和x2，且x1<x2，f（x1）*f（x2）＜0，则在（x1，x2）之间一定有一个根。输入：a，b，c，d输出：三个实根（根与根之间留有空格）输入输出样例输入：1-5-420输出：-2.002.005.00【算法分析】这是一道有趣的解方程题。为了便于求解，将原方程f(x)=ax3+bx2+cx+d＝0变换成f’(x)=x3+b’x2+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的根。有两种方法计算f’(x)=0的根x:1．枚举法根据根的值域和根与根之间的间距要求（≥1），我们不妨将根的值域扩大100倍（-10000≤x≤10000），依次枚举该区间的每一个整数值x，并在题目要求的精度内设定区间：若区间端点的函数值f’(x1)和f’(x2)异号或者在区间端点x1的函数值f’(x1)=0，则确定为f’(x)=0的一个根。由此得出算法：2.分治法枚举根的值域中的每一个整数x(-100≤x≤100)。由于根与根之差的绝对值≥1，因此设定搜索区间[x1，x2]，其中x1=x，x2=x+1。若⑴f’(x1)=0，则确定x1为f’(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)≤0，则确定根在左区间[x1，x]内，将x设为该区间的右指针（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地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。【问题输入】仅一行，三个数据分别表示AB两地的距离s，人的步行速度a，车的速度b。【问题输出】两人同时到达B地需要的最短时间。【输入输出样例】car.in120525car.out9.6000000000E+00【算法分析】最佳方案为：甲先乘车到达K处后下车步行，小车再回头接已走到C处的乙，在D处相遇后，乙再乘车赶往B，最后甲、乙一起到达B地。如下图所示，这时所用的时间最短。这样问题就转换成了求K处的位置，我们用二分法，不断尝试，直到满足同时到达的时间精度。算法框架如下：1、输入s，a，b；2、c0:=0；c1:=s；c:=(c0+c1)/2；3、求t1，t2；4、如果t1<t2，那么c:=(c0+c)/2否则c:=(c+c1)/2；反复执行3和4，直到abs(t1-t2)满足精度要求（即小于误差标准）。参考程序（略）【例5】循环比赛日程表（match.???）设有n个选手的循环比赛，其中n=2m，要求每名选手要与其他n-1名选手都赛一次。每名选手每天比赛一次，循环赛共进行n-1天。要求每天没有选手轮空.以下是八名选手时的循环比赛表，表中第一行为八位选手的编号，下面七行依次是每位选手每天的对手。1234567821436587341278564321876556781234658721437856341287654321[问题分析]从八位选手的循环比赛表中可以看出,这是一个具有对称性的方阵,可以把方阵一分为四来看,那么左上角的4*4的方阵就是前四位选手的循环比赛表,而右上角的4*4的方阵就是后四位选手的循环比赛表,它们在本质上是一样的,都是4个选手的循环比赛表,所不同的只