资源描述：
《天津科技大学算法设计与分析第5章减治法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第5章减治法5.1减治法的设计思想5.2查找问题中的减治法5.3排序问题中的减治法5.4组合问题中的减治法7/21/20211算法设计与分析--减治法5.1减治法的设计思想规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系：（1）原问题的解只存在于其中一个较小规模的子问题中；（2）原问题的解与其中一个较小规模的解之间存在某种对应关系。由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。7/21/20212算法设计与分析--减治法子问题的规模是n/2子问题的解原问题的解原问题的规模是n减治法的设计
2、思想7/21/20213算法设计与分析--减治法例：计算an的值，应用减治技术得到如下计算方法：应用分治法得到an的计算方法是：O(log2n)O(nlog2n)ïîïíì>´>==-且是奇数且是偶数1)(1)(122)1(22naananaannn7/21/20214算法设计与分析--减治法应用减治法处理问题的效率一般是O(log2n)数量级。减治法只对一个子问题求解，并且不需要进行解的合并。应用减治法（例如减半法）得到的算法通常具有如下递推式：7/21/20215算法设计与分析--减治法5.2查找问题中的减治法5.2.1折半查找5.2.2二叉查找树7/21/20216算法
3、设计与分析--减治法基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。5.2.1折半查找[r1………rmid-1]rmid[rmid+1………rn]（mid=(1+n)/2）如果krmid查找这里k7/21/20217算法设计与分析--减治法例：查找值为14的记录的过程：012345678910111213714182123293
4、1353842464952low=1high=13mid=7high=6mid=3high=2mid=131>1418>147<14low=2mid=214=147/21/20218算法设计与分析--减治法算法5.1——折半查找1.low=1；high=n；//设置初始查找区间2.测试查找区间［low，high］是否存在，若不存在，则查找失败；否则3.取中间点mid=(low+high)/2;比较k与r[mid]，有以下三种情况：3.1若kr[mid]，则low=mid+1；查找在右半区进行，转2；3
5、.3若k=r[mid]，则查找成功，返回记录在表中位置mid；伪代码7/21/20219算法设计与分析--减治法判定树——描述折半查找的判定过程。长度为n的判定树的构造方法为：（1）当n=0时，判定树为空；（2）当n＞0时，判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1]~r[mid-1]相对应的判定树，根结点的右子树是与r[mid+1]~r[n]相对应的判定树。7/21/202110算法设计与分析--减治法具有11个结点的判定树6312548111079在表中查找任一记录的过程，即是判定树中从根结点到该记录结点的路径，和给定值的比
6、较次数等于该记录结点在树中的层数。具有n个结点的判定数的深度为。7/21/202111算法设计与分析--减治法5.2.2二叉查找树由二叉排序树的定义，在二叉排序树root中查找给定值k的过程是：⑴若root是空树，则查找失败；⑵若k＝根结点的值，则查找成功；⑶否则，若k＜根结点的值，则在root的左子树上查找；⑷否则，在root的右子树上查找；上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。二叉排序树的查找效率就在于只需要查找两个子树之一。7/21/202112算法设计与分析--减治法(a)按63,90,55,58,70,42,10,45,8
7、3,67(b)按55,42,10,70,63,58,83,67,90,45的顺序构造的二叉排序树的顺序构造的二叉排序树58427090634555836710108363705545426758907/21/202113算法设计与分析--减治法二叉排序树的结点结构为：structBiNode{intdata;//结点的值，假设查找集合的元素为整型BiNode*lchild,*rchild;//指向左、右子树的指针};算法5.2——二叉排序树的查找BiNode*SearchBST(BiNode*root,
