第5章减治法.ppt

第5章减治法
减治法的设计思想
查找问题中的减治法
组合问题中的减治法
减治法的设计思想
规模为n的原问题的解与较小规模(通常是n/2)的子问题的解之间具有关系:
(1)原问题的解只存在于其中一个较小规模的子问题中;
(2)原问题的解与其中一个较小规模的解之间存在某种对应关系。
由于原问题的解与较小规模的子问题的解之间存在这种关系,所以,只需求解其中一个较小规模的子问题就可以得到原问题的解。
子问题
的规模是n/2
子问题的解
原问题的解
原问题
的规模是n
减治法的设计思想
例:计算an的值,应用减治技术得到如下计算方法:
应用分治法得到an的计算方法是:
O (log2n)
O (nlog2n)
ï
î
ï
í
ì
>
´
>
=
=
-
且是奇数
且是偶数
1
)
(
1
)
(
1
2
2
)
1
(
2
2
n
a
a
n
a
n
a
a
n
n
n
所以,通常来说,应用减治法处理问题的效率是很高的,一般是O(log2n)数量级。
减治法只对一个子问题求解,并且不需要进行解的合并。应用减治法(例如减半法)得到的算法通常具有如下递推式:
查找问题中的减治法
折半查找
基本思想:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键码相等,则查找成功;若给定值小于中间记录的关键码,则在中间记录的左半区继续查找;若给定值大于中间记录的关键码,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。
折半查找
[ r1 ……… rmid-1 ] rmid [ rmid+1 ……… rn ] (mid=(1+n)/2)
如果k<rmid查找这里如果k>rmid查找这里
k
例:查找值为14的记录的过程:
0 1 2 3 4 5 6 7 8 9 10 11 12 13
7 14 18 21 23 29 31 35 38 42 46 49 52
low=1
high=13
mid=7
high=6
mid=3
high=2
mid=1
31>14
18>14
7<14
low=2
mid=2
14=14
组合问题中的减治法
淘汰赛冠军问题
假币问题
淘汰赛冠军问题
假设有n=2k个选手进行竞技淘汰赛,最后决出冠军的选手,用函数
p(string mem1, string mem2);
模拟两位选手的比赛,p返回TRUE ,p返回FALSE,p的执行,下面的算法实现选手的竞技淘汰比赛的过程。