第5章 减治法

《第5章 减治法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章减治法5.1减治法的设计思想5.2查找问题中的减治法5.3排序问题中的减治法5.4组合问题中的减治法5.1减治法的设计思想规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系：（1）原问题的解只存在于其中一个较小规模的子问题中；（2）原问题的解与其中一个较小规模的解之间存在某种对应关系。由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。子问题的规模是n/2子问题的解原问题的解原问题的规模是n减治法的设计思想例：计算an的值，应用减治技术得到如下计算方法：

2、应用分治法得到an的计算方法是：O(log2n)O(nlog2n)ïîïíì>´>==-且是奇数且是偶数1)(1)(122)1(22naananaannn所以，通常来说，应用减治法处理问题的效率是很高的，一般是O(log2n)数量级。减治法只对一个子问题求解，并且不需要进行解的合并。应用减治法（例如减半法）得到的算法通常具有如下递推式：5.2查找问题中的减治法5.2.1折半查找5.2.2二叉查找树基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查

3、找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。5.2.1折半查找[r1………rmid-1]rmid[rmid+1………rn]（mid=(1+n)/2）如果krmid查找这里k例：查找值为14的记录的过程：0123456789101112137141821232931353842464952low=1high=13mid=7high=6mid=3high=2mid=131>1418>147<14low=2mid=214=14算法5.1—

4、—折半查找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.3若k=r[mid]，则查找成功，返回记录在表中位置mid；伪代码判定树——描述折半查找的判定过程。长度为n的判定树的构造方法为：（1）当n=0时，判定树为空；（2）当n＞0时，判

5、定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1]~r[mid-1]相对应的判定树，根结点的右子树是与r[mid+1]~r[n]相对应的判定树。具有11个结点的判定树6312548111079在表中查找任一记录的过程，即是判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。具有n个结点的判定数的深度为。5.2.2二叉查找树由二叉排序树的定义，在二叉排序树root中查找给定值k的过程是：⑴若root是空树，则查找失败；⑵若k＝根结点的值，则查找成功；⑶否则，若k＜根结点的值

6、，则在root的左子树上查找；⑷否则，在root的右子树上查找；上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。二叉排序树的查找效率就在于只需要查找两个子树之一。(a)按63,90,55,58,70,42,10,45,83,67(b)按55,42,10,70,63,58,83,67,90,45的顺序构造的二叉排序树的顺序构造的二叉排序树5842709063455583671010836370554542675890二叉排序树的结点结构为：structBiNode{intdata;//结点的值，假设查找集合的

7、元素为整型BiNode*lchild,*rchild;//指向左、右子树的指针};算法5.2——二叉排序树的查找BiNode*SearchBST(BiNode*root,intk){if(root==NULL)returnNULL；elseif(root->data==k)returnroot;elseif(kdata)returnSearchBST(root->lchild,k);elsereturnSearchBST(root->rchild,k);}C++描述在二叉排序树上查找关键码等于给定值的结点的过程，恰好走了一条从

8、根结点到该结点的路径，和给定值的比较次数等于给定值的结点在二叉排序树中的层数，比较次数最少为1次（即整个二叉排序树的根结点就是待查结点），最多不超过树的深度。具有n个结点的二叉树