第7章分治算法

1、第七章第七章 分治算法分治算法 所谓分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。 1、解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的： 解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量 决定）合并所有子问题所需的工作量。2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法。

2、 3、分治的具体过程（以二分法为例）： begin 开始 if 问题不可分 then 返回问题解 else begin 从原问题中划出含一半运算对象的子问题1； 递归调用分治法过程，求出解1； 从原问题中划出含另一半运算对象的子问题2； 递归调用分治法过程，求出解2； 将解1、解2组合成整个问题的解；end; end; /结束【例【例1】快速排序快速排序(递归算法递归算法)procedure qsort(l,r:integer);var i,j,mid,p:integer;begin i:=l; j:=r; mid:=a(l+r) div 2; /将当前序列在中间位置的数定义为中间数 repe

3、at while aimid do dec(j); /在右半部分寻找比中间数小的数 if ij; if lj then qsort(l,j); /若未到两个数的边界，则递归搜索左右区间 if iy then writeln(no find) /找不到该数找不到该数 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); /输入排序好的数输入排序好的数 readln(m); /输入要查找的数输入要查找的数 jc(x,y); /递归

4、过程递归过程 readln;end.【例【例3】一元三次方程求解一元三次方程求解 有形如：ax3+bx2+cx+d0这样的一个一元三次方程。给出该方程中各项的系数（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 -

5、4 20 输出：-2.00 2.00 5.00【算法分析】【算法分析】 这是一道有趣的解方程题。为了便于求解，设方程f(x)=ax3+bx2+cx+d0，设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 x10000)，依次枚举该区间的

6、每一个整数值x，并在题目要求的精度内设定区间：x1=，x2=。若区间端点的函数值f(x1)和f(x2)异号或者在区间端点x1的函数值f(x1)=0，则确定为f(x)=0的一个根。由此得出算法： 输入方程中各项的系数a，b，c，d ； for x-10000 to 10000 do /枚举当前根*100的可能范围 begin x1(x-0.05)/100；x2(x+0.05)/100；/在题目要求的精度内设定区间 if (f(x1)*f(x2)0，则确定根x不在区间x1，x2内，设定x2，x2+1为下一个搜索区间 f(x1)*f(x2)0，则确定根x在区间x1，x2内。 如果确定根x在区间x1，

7、x2内的话（f(x1)*f(x2)0，则确定根在右区间x，x2内，将x设为该区间的左指针（x1=x），继续对右区间进行对分； 上述对分过程一直进行到区间的间距满足精度要求为止（x2-x10.001）。此时确定x1为f(x)的根。由此得出算法：输入方程中各项的系数a，b，c，d ；for x-100 to 100 do /枚举每一个可能的根 begin x1x；x2x+1； /确定根的可能区间 if f(x1)=0 then write(x1:0:2， ) /若x1为根，则输出 else if (f(x1)*f(x2)=0.001 do /若区间x1，x2不满足精度要求，则循环 begin xx

8、(x2+x1)/2； /计算区间x1，x2的中间位置 if f(x1)*f(xx)=0 then x2xx /若根在左区间，则调整右指针 else x1xx； /若根在右区间，则调整左指针 end；/while write(x1:0:2， )； /区间x1，x2满足精度要求，确定x1为根 end； /then end； /for其中f(x)的函数说明如枚举法所示。【例【例4】小车问题（小车问题（car）【问题描述】【问题描述】 甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能

9、使两人尽快同时到达。【输入格式】【输入格式】 仅一行，三个数据分别表示AB两地的距离s，人的步行速度a，车的速度b。【输出格式】【输出格式】 两人同时到达B地需要的最短时间。【输入样例】【输入样例】car.in120 5 25【输出样例】【输出样例】car.out9.6000000000E+00【算法分析】【算法分析】 最佳方案为：甲先乘车到达K处后下车步行，小车再回头接已走到C处的乙，在D处相遇后，乙再乘车赶往B，最后甲、乙一起到达B地。如下图所示，这时所用的时间最短。这样问题就转换成了求K处的位置，我们用二分法，不断尝试，直到满足同时到达的时间精度。算法框架如下： 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；反复执行3和4，直到abs(t1-t2)满足精度要求（即小于误差标准）。【参考程序】【参考程序】program 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)个数据先分成两组，分别求最大值、最小值，然后分别将两组的最大值和最小值进行比较，求出全部元素的最大值和最小值。若分组后元素还大于2，则再次分组，直至组内元素小于等于2。 策略二：如果N等于1时，MAX=MIN=A1，如果N=2时，MAX=A1，MIN=A2或MAX=A2，MIN=A1，这是

12、非常简单的，所以此题可把所有的数作为一个序列，每次从中取出开头两个数，求共MAX，MIN，然后再从剩余的数中取开头两个数，求其MAX、MIN后与前一次的MAX、MIN比较，可得出新的MAX、MIN，这样重复下去，直到把所有的数取完（注意最后一次取可能是只有一个数），MAX，MIN也就得到了。这就是典型的分治策略。注意：这样做与把所有数字排序后再取MAX、MIN要快得多。3、方程、方程f(x)的根的根【问题描述】【问题描述】 求方程f(x)=2x+3x-4x=0在1，2内的根。 提示：2x可以表示成exp(x*ln(2)的形式。【输入格式】 输入：1，2的区间值。【输出格式】 输出：方程f(x)

13、=0的根，x的值精确小数点10位。【输入样例】 1 2【输出样例】 1.50711059574、求一元三次方程的解、求一元三次方程的解【问题描述】【问题描述】 有形如： ax3+bx2+cx+d=0一元三次方程。给出该方程中各项的系数 (a， b， c， d 均为实数 )，并约定该方程存在三个不同实根 (根的范围在 -100至 100之间 )，且根与根之差的绝对值 =1。要求由小到大依次在同一行上输出这三个实根。 【输入格式】【输入格式】 输入：a，b，c，d【输出格式】【输出格式】 输出： 三个实根（根与根之间留有空格）【输入样例】【输入样例】Equ.in1 5 4 20【输出样例】【输出样例】Equ.out-2.00 2.00 5.005、求逆序对、求逆序对 给定一个序列a1,a2,an，如果存在iaj，那么我们称之为逆序对，求逆序对的数目。【输入格式】 第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。【输出格式】 所有逆序对总数。【输入样例】deseq. in43232【输出样例】deseq.out3【数据范围】N=105，Ai=105。6、小车问题（、小车问题（car）【问题描述】【问题描述】 甲、乙两人同时从A地出发要尽快