算法设计与分析_王红梅_第6章 动态规划法.ppt

算法设计与分析_王红梅_第6章 动态规划法.ppt第5章减治法 减治法的设计思想 查找问题中的减治法 排序问题中的减治法 组合问题中的减治法 减治法的设计思想规模为 n 的原问题的解与较小规模(通常是 n /2)的子问题的解之间具有关系: (1 )原问题的解只存在于其中一个较小规模的子问题中; (2 )原问题的解与其中一个较小规模的解之间存在某种对应关系。由于原问题的解与较小规模的子问题的解之间存在这种关系,所以,只需求解其中一个较小规模的子问题就可以得到原问题的解。子问题的规模是 n /2子问题的解原问题的解原问题的规模是 n 减治法的设计思想例:计算 a n的值, 应用减治技术得到如下计算方法: 应用分治法得到 a n的计算方法是: ???????????1 1 22naa naa nn n O ( log 2n) O (n) ???????????且是奇数且是偶数 1)( 1)( 1 22 )1( 22naa na naa n nn1 11)2/( 0)(???????n nnT nT所以,通常来说,应用减治法处理问题的效率是很高的,一般是 O( log 2n)数量级。减治法只对一个子问题求解,并且不需要进行解的合并。应用减治法(例如减半法)得到的算法通常具有如下递推式: 查找问题中的减治法 折半查找 二叉查找树基本思想:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键码相等,则查找成功;若给定值小于中间记录的关键码,则在中间记录的左半区继续查找; 若给定值大于中间记录的关键码,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。 折半查找[ r 1………r mid - 1 ] r mid [ r mid +1………r n ] ( mid =(1+ n) /2) 如果 k<r mid查找这里如果 k>r mid查找这里 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 算法 ——折半查找 1. low=1 ; high=n ; //设置初始查找区间 2. 测试查找区间[ low , high ]是否存在,若不存在,则查找失败; 否则 3. 取中间点 mid= ( low+high ) /2; 比较 k与 r[mid] ,有以下三种情况: 若 k<r[mid] ,则 high=mid -1;查找在左半区进行,转 2; 若 k>r[mid] ,则 low=mid+1 ;查找在右半区进行,转 2; 若 k=r[mid] ,则查找成功,返回记录在表中位置 mid ; 判定树——描述折半查找的判定过程。长度为 n的判定树的构造方法为: (1)当 n =0 时,判定树为空; (2)当 n>0时,判定树的根结点是有序表中序号为 mid=(n+1)/2 的记录,根结点的左子树是与有序表 r[1] ~ r[mid-1] 相对应的判定树,根结点的右子树是与 r[mid+1] ~ r[n ]相对应的判定树。