文档介绍：第七章分治算法
所谓分治就是指的分而治之,即将较大规模的问题分解成几个较小规模的问题,通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。
分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。找出各部分的解,然后把各部分的解组合成整个问题的解。
1、解决算法实现的同时,需要估算算法实现所需时间。分治算法时间是这样确定的: 解决子问题所需的工作总量(由子问题的个数、解决每个子问题的工作量决定)合并所有子问题所需的工作量。
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]; //将当前序列在中间位置的数定义为中间数
repeat
while a[i]<mid do inc(i); //在左半部分寻找比中间数大的数
while a[j]>mid do dec(j); //在右半部分寻找比中间数小的数
if i<=j then
begin //若找到一组与排序目标不一致的数对则交换它们
p:=a[i];
a[i]:=a[j];
a[j]:=p;
inc(i); dec(j); //继续找
end;
until i>j;
if l<j then qsort(l,j); //若未到两个数的边界,则递归搜索左右区间
if i<r then qsort(i,r);
end;//sort
【例2】用递归算法实现二分查找即:有20个已经从小到大排序好的数据,输入一个数X,用二分查找算法,判断它是否在这20个数中。
program ex11_2;
var a:array[1..20]of integer;
n,i,m,x,y:integer;
procedure jc(x,y:integer); //递归过程
var k:integer;
begin
k:=(x+y)div 2; //取中间位置点
if a[k]=m then writeln('then num in',k:5); //找到查找的数,输出结果
if x>y then writeln('no find') //找不到该数
else begin
if a[k]<m then jc(k+1,y); //在后半中查找
if a[k]>m then jc(x,k-1); //在前半中查找
end;
end;
begin
readln(n);
x:=1;y:=n;
for i:=1to n do readln(a[i]); //输入排序好的数
readln(m); //输入要查找的数
jc(x,y); //递归过程
readln;
end.
【例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 -4 20 输出:-
【算法分析】
这是一道有趣的解方程题。为了便于求解,设方程f(x)=ax3+bx2+cx+d=0,设x的值域(-100至100之间)中有x, ,即 x1=x-,x2=x+。x1和x2间的距离()满足精度要求(精确到小数点后2位)。若出现如图1所示的两种情况之一,则确定x为f(x)=0的根。
有两种方法计算f(x)=0的根x:
根据根的值域和根与根之间的间距要求(≥1),我们不妨将根的值域扩大100倍(-1