基础算法5-分治法

1、基础算法分治法一、分治思想一、分治思想n 分治法，又叫分治策略，顾名思义，。n 它的基本思想：对于难以直接解决的规模较大的问题，把它分解成若干个能直接解决的相互独立的子问题，递归求出各子问题的解，再合并子问题的解，得到原问题的解。n 通过减少问题的规模，逐步求解，能够明显降低解决问题的复杂度。二、分治法的适用条件二、分治法的适用条件n 使用分治法解决问题，一般分为三个步骤： 分解（Divide）：将要解决的问题分解成若干个规模较小的同类子问题； 解决（Conquer）：当子问题划分得足够小时，求解出子问题的解。 合并（Combine）：将子问题的解逐层合并成原问题的解。n 分治法在信息学竞赛中

2、应用非常广泛，使用分治策略能生成一些常用的算法和数据结构，如快排、最优二叉树、线段树等；还可以直接使用分治策略，解决一些规模很大、无法直接下手的问题。分治算法设计过程图分治算法设计过程图n在划分问题时，可以采用递归策略，把一个大问题逐步分解成规模较小的子问题，直至可以直接求出子问题的解；再将子问题逐层合并，返回到顶层，得到原问题的解。n根据分治策略的划分原则，一般把原问题每次划分成2个子问题、每个子问题的规模差不多最合适。合并解时要因题而异，有些问题递归分解完能直接得到原问题的解，有些问题需逐层合并，得到原问题的解。四、分治的框架结构四、分治的框架结构procedure Divide()beg

3、in if(问题不可分问题不可分)then/解决解决 begin 直接求解；直接求解； 返回问题的解；返回问题的解； end else begin 对原问题进行分治；对原问题进行分治；/分解分解 递归对每一个分治的部分进行求解递归对每一个分治的部分进行求解; /解决解决 归并整个问题，得出全问题的解归并整个问题，得出全问题的解; /合并合并 endend;n 例题例题1：给：给n个数，求它们之中最大值和最小值，要求比较个数，求它们之中最大值和最小值，要求比较次数尽量小。次数尽量小。分析：分析：假设数据个数为n,存放在数组a1.n中。可以直接进行比较： minn:=a1;maxx:=a1; fo

4、r i:=2 to n do if aimaxx then maxx:=ai; else if aixr1 then begin maxx:=xr2; minn:=xr1; end else begin maxx:=xr1; minn:=xr2; end end else begin d:=(r1+r2) div 2; 找到中间位置找到中间位置 pd(r1,d,max1,min1); 比较第一段的值比较第一段的值 pd(d+1,r2,max2,min2); 比较第二段的值比较第二段的值 if max1max2 then maxx:=max1 求出最大值求出最大值 else maxx:=max2

5、; if min1=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。【文件输入文件输入】输入仅一行，有四个数，依次为a、b、c、d【文件输出文件输出】输出也只有一行，即三个根(从小到大输出)【样例输入样例输入】1 -5 -4 20【样例输入样例输入】-2.0000 2.0000 5.0000n 如果精确到小数点后两位，可用简单枚举法：将x从-100.00 到100.00（步长0.01）逐一枚举，得到20000个 f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而题目已改成精度为小数点后4位，枚举算法时间复杂度将达不到要求。n 直接使用求根公式

6、，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值。n A.当已知区间当已知区间(a,b)内有一个根时；内有一个根时；n 用二分法求根，若区间(a,b)内有根，则必有f(a)*f(b)b或f(a+b)/2)=0，则可确定根为(a+b)/2并退出过程； 、若f(a)*f(a+b)/2)0,则必然有f(a+b)/2)*f(b)=1。因此可知：在-100,-99、-99,-98、99，100、100，100这201个区间内，每个区间内至多只能有一个根。即：除区间100，100外，其余区间a,a+1，只有当f(a)=0或f(a)*f(a+1)0时，方程在此区间

7、内才有解。若f(a)=0 ，解即为a；若f(a)*f(a+1)0 ，则可以利用A中所述的二分法迅速出找出解。如此可求出方程的所有的解。program fangcheng;var a,b,c,d,x,p,q:real; anx:array1.3of real; i,t:integer;function f(x:real):real; 计算计算f(x)的值的值begin f:=(a*x+b)*x+c)*x+d;end;function findx(i:real):real; 用分治法在已知有根的区间用分治法在已知有根的区间i,i+1里找里找到一个解到一个解begin p:=i; 从从i开始找起开始

8、找起 q:=p+0.99999; 在误差范围内，在误差范围内，q近似等于近似等于i+1 if abs(f(p)0.00001 then findx:=p 当当f(x)的值误差小于小数点后的值误差小于小数点后4位则得到一个解位则得到一个解p else begin while(p+0.0001q)and(f(p+q)/2)0) do p小于小于q且中间且中间值计算结果不为值计算结果不为0 if f(p)*f(p+q)/2)0 如果解在如果解在p,(p+q)/2区间内区间内 then q:=(p+q)/2 开始在开始在p,(p+q)/2区间内找解区间内找解 else p:=(p+q)/2; 否则在否则在(p+q)/2,q区间内找解区间内找解 findx:=(p+q)/2; 每次都二分查找值每次都二分查找值 end;end;begin read(a,b,c,d); t:=0; t为解的个数为解的个数 for i:=-100 to 100 do begin if (abs(f(i)0.00001)or(f(i)*f(i+0.99999)=0) 当区间当区间