分治算法策略.docVIP

分治策略(3) 【例3】一元三次方程求解 有形如：ax3 +bx2 +cx+d＝0这样的一个一元三次方程。给出该方程中各项的系数（a，b，c，d 均为实数），并约定该方程存在三个不同实根（根的范围在-100 至 100 之间），且根与根之差的绝对值≥1。 要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后 2 位。 提示：记方程 f（x）=0，若存在 2 个数 x1 和 x2，且 x1x2，f（x1）*f（x2）＜0， 则在（x1，x2）之间一定有一个根。 输入： a，b，c，d 输出： 三个实根（根与根之间留有空格） 输入输出样例 输入： 1 -5 -4 20 输出： -2.00 2.00 5.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-x10.001）。此时确定 x1 为f’(x)的根。 由此得出算法： 其中f(x)的函数说明如枚举法所示。 【例4】小车问题（car） 【问题描述】 甲、乙两人同时从A地出发要尽快同时赶到 B地。出发时A 地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。 【问题输入】 仅一行，三个数据分别表示 AB两地的距离s，人的步行速度a，车的速度 b。 【问题输出】 两人同时到达B地需要的最短时间。 【输入输出样例】 car.in 120 5 25 car.out 9.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、如果t1t2，那么c:=(c0+c)/2否则c:=(c+c1)/2； 反复执行3和4，直到abs(t1-t2)满足精度要求（即小于误差标准）。 参考程序（略） 【例5】循环比赛日程表（match.???） 设有n个选手的循环比赛，其中n=2m，要求每名选手要与其他n-1名选手都赛一次。每名选手每天比赛一次，循环赛共进行n-1天。要求每天没有选手轮空.以下是八名选手时的循环比赛表，表中第一行为八位选手的编号，下面七行依次是每位选手每天的对手。