一、算法思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题规模越小,解题所需的计算时间往往也越少,从而也越容易计算。想解决一个较大的问题,有时是相当困难的。分治法的思想就是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。找出各部分的解,然后把各部分的解组合成整个问题的解。
1、解决算法实现的同时,需要估算算法实现所需时间。分治算法时间是这样确定的:
解决子问题所需的工作总量(由 子问题的个数、解决每个子问题的工作量 决定)
合并所有子问题所需的工作量
2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法
3、分治的具体过程:
begin {开始}
if ①问题不可分 then ②返回问题解
else begin
③从原问题中划出含一半运算对象的子问题1;
④递归调用分治法过程,求出解1;
⑤从原问题中划出含另一半运算对象的子问题2;
⑥递归调用分治法过程,求出解2;
⑦将解1、解2组合成整修问题的解;
end;
end; {结束}
二、例题分析
1、[金块问题]老板有一袋金块(共n块,n是2的幂(n>=2)),将有两名最优秀的雇员每人得到其中的一块,排名第一的得到最重的那块,排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器,我们希望用最少的比较次数找出最重的金块。
分析:问题可以简化为:在含n(n是2的幂(n>=2))个元素的集合中寻找极大元和极小元。
明显的方法是逐个的进行比较查找。
(一次冒泡排序) |
(或者一次选择排序) p:=1; for i:=2 to n do if a[p]<a[i] then p:=i; m:=a[p]; |
需要n-1次比较得到max,而再经过n-2次比较得到min,共进行2*n-3次比较可以找出极大元和极小元。
用分治法可以较少比较次数地解决上述问题:
如果集合中只有1个元素,则它既是最大值也是最小值;
如果有2个元素,则一次maxnum(i,j) 一次minnum(i,j)就可以得到最大值和最小值;
如果把集合分成两个子集合,递归的应用这个算法分别求出两个子集合的最大值和最小值,最后让子集合1的最大值跟子集合2的最大值比较得到整个集合的最大值;让子集合1的最小值跟子集合2的最小值比较得到整个集合的最小值。
可得解题思想:
{maxmin}
①if 问题不可分:n=2
②问题的解求得(两个元素时):对两元素进行比较;return;
③for i:=1 to n div 2 do b[i]:=a[i]
④maxmin(n div 2,b,max1,min1),其中max1和min1为解1
⑤for i:=1 to n div 2 do b[i]:=a[i+ n div 2]
⑥maxmin(n div 2,b,max2,min2),其中max2和min2为解2
⑦max:=maxnum(max1,max2);
min:=minnum(min1,min2);
{maxmin}
其中对函数maxnum的求精:
function maxnum(a,b:integer):integer;
begin
if a>b then maxnum:=a else maxnum:=b;
end;
分析比较次数:
比较运算均在函数maxnum和minnum中进行,
当n=2时,比较次数T(n)=1
当n>2时,比较次数T(n)=2T(n/2)+2
∵n是2的k次幂
∴设n=2^k
?
2、快速排序
快速排序是基于分治策略的一个排序算法。按照分治法的思想分析快速排序:
(1)分解(Divide) 以元素a[p]为基准元素将a[p:q-1]划分为三段a[p:q-1],a[q]和a[q+1:r],使得a[p:q-1]中任何一个元素都小于a[q],a[q+1:r]中任何一个元素大于等于a[q],下标q在划分中确定。
(2)递归求解(Conquer) 通过递归调用快速排序算法分别对a[p:q-1] 和a[q+1:r]进行排序。
(3)合并(Merge) 由于a[p:q-1] 和a[q+1:r]的排序都是在原位置进行的,所以不必进行任何合并操作就已经排好序了。
在上面三个步骤中,第一步:分解是关键。一次快速排序确定划分元素的位置,具体参见排序算法----快速排序
3、归并排序
归并排序也是基于分治策略的另一个算法。归并的思路是把两个已经排好序的数组合并为一个。(源程序)
2-路归并排序示例:
初始值 |
E |
Y |
U |
K |
S |
L |
B |
一趟归并排序 |
E Y |
K U |
L S |
B | |||
两趟归并排序 |
E K U Y |
B L S | |||||
三趟归并排序 |
B E K L S U Y |
procedure mergesort(var r,r1:listtype;s,t:integer);
{r,r1:均为链表,存储排序数据;过程mergesort(r,r1,s,t)完成把链表r中的关键字进行归并排序、并存放到链表r1中,其中s是下界t是上界}
{过程merge(r2,s,m,t,r1)把链表r2中排好序的子链r2[s..m]和子链r2[m+1..t]合并到r1中}
if 问题不可分 then 求解 |
if s=t then r1[s]:=r[s] |
else | else |
(1)分出问题的一个子问题1,并求解子问题1 | mergesort(r,r2,s,(s+t)div 2); |
(2)分出问题的一个子问题2,求解子问题2 | mergesort(r,r2,(s+t)div 2,t); |
(3)合并子问题1和子问题2 | merge(r2,s,(s+t)div 2,t,r1); |
4、[循环赛问题](1999年广东省青少年信息学奥林匹克竞赛 第三题:棒球联赛)
问题描述:广州市体委将举行一次由N支队伍(队伍编号为1..N)参加的少年棒球联赛。联赛总共不能多于N轮(同一时间内若干支队进行一次比赛为一轮),并且每两支队之间必须而且仅必须进行一次比赛。请编程为这次比赛设计一个赛程表。
循环赛问题可以用分治法解决。下面是先假定n=2^k
procedure table(k:integer;a:array[1..u1,1..u2] of integer);
var n,i,j,m,s,t:integer;
begin
n:=1;
for i:=1 to k do n:=n*2;
for i:=1 to n do a[1,i]:=i;
m:=1;
for s:=1 to k do
begin
n:=n / 2;
for t:=1 to n do
for i:=m+1 to 2*m do
for j:=m+1 to 2*m do
begin
a[i,j+(t-1)*m*2]:=a[i-m,j+(t-1)*m*2-m];
a[i,j+(t-1)*m*2-m]:=a[i-m,j+(t-1)*m*2];
end;
m:=m*2;
end;{for s}
end;
三、练习题
[二分检索]假定在A[1..9]中顺序存放这九个数:-7,-2,0,5,16,43,57,102,291 要求检索291,16,101是否在数组中。
给定已排好序的n个元素A1,A2,A3,…,An, 找出元素x是否在A中,如果x在A中,指出它在A中的位置。
五年级上册解方程练… | 255457 |
九连环图解解法 | 226892 |
wifi万能钥匙破解的… | 177863 |
纸飞机Skyking(空… | 170844 |
小学语文知识大全(… | 152076 |
各种鱼钩鱼线绑法与… | 117013 |
课题研究的方法有哪些 | 113473 |
人教版pep小学英语… | 104571 |
小学语文知识大全(… | 96818 |
人教版pep小学英语… | 96209 |
小学数学五年级上册… | 93451 |
人教版pep小学英语… | 82587 |
小学语文知识大全(… | 80413 |
笔记本电脑如何关闭… | 79825 |
小学生六一搞笑小品… | 78892 |
不打结的红领巾系法… | 78083 |