第5章 减治法Decrease and conquer.pptx

第5章 减治法(Decrease and conquer）;5.1 减治法的设计思想 ;5.1 减治法的设计思想 ;;例：计算an的值; 34;应用分治法（例如二分法）得到的算法通常具有如下递推式： ;应用分治法（例如二分法）得到的算法通常具有如下递推式： ;5.2 查找问题中的减治法 ;问题描述： 应用折半查找方法在一个有序序列中查找值为k的记录。若查找成功，返回记录k在序列中的位置，若查找失败，返回失败信息。 ;折半查找利用了记录序列有序的特点，其查找过程是： 在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功； 若给定值小于中间记录的关键码，则在中间记录的左半区继续查找； 若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。 不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。 ;0 1 2 3 4 5 6 7 8 9 10 11 12 13;算法——折半查找 1. low=1；high=n； //设置初始查找区间 2. 测试查找区间［low，high］是否存在，若不存在，则查找失败； 否则 3. 取中间点mid=(low+high)/2; 比较k与r[mid] 有以下三种情况： 3.1 若kr[mid]，则high=mid-1；查找在左半区进行，转2； 3.2 若kr[mid]，则low=mid+1；查找在右半区进行，转2； 3.3 若k=r[mid]，则查找成功，返回记录在表中位置mid。;;具有11个结点的判定树; 在一个无序序列中执行查找操作，可以将无序序列建立一棵二叉查找树，然后在二叉查找树中查找值为k的记录，若查找成功，返回记录k的存储地址，若查找失败，返回空指针。;二叉查找树的定义;(a) 按63,90,55,58,70,42,10,45,83,67 (b) 按55,42,10,70,63,58,83,67,90,45 的顺序构造的二叉查找树 的顺序构造的二叉查找树; 由二叉查找树的定义，在二叉查找树root中查找给定值k的过程是： ⑴ 若root是空树，则查找失败； ⑵ 若k＝根结点的值，则查找成功； ⑶ 否则，若k＜根结点的值，则在root的左子树上查找； ⑷ 否则，在root的右子树上查找； 上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。;在二叉查找树中查找关键字值为35，95的过程：;二叉查找树的结点结构为： struct BiNode { int data; //结点的值，假设查找集合的元素为整型 BiNode *lchild, *rchild; //指向左、右子树的指针 };; 在二叉排序树上查找关键码等于给定值的结点的过程，恰好走了一条从根结点到该结点的路径，和给定值的比较次数等于给定值的结点在二叉排序树中的层数，比较次数最少为1次（即整个二叉排序树的根结点就是待查结点），最多不超过树的深度。 具有n个结点的二叉树的深度至少是 ，至多是n。所以，二叉排序树的查找性能在O(log2n)和O(n)之间。 ; 设无序序列 T =(r1, r2, …, rn)，T 的第k（1≤k≤n）小元素定义为T按升序排列后在第k个位置上的元素。给定一个序列T和一个整数k，寻找 T 的第k小元素的问题称为选择问题。 特别地，将寻找第n/2小元素的问题称为中值问题。 ;问题描述： 在n个元素的无序数组中选择第k(1=k=n)小元素。 当k=1时，相当于找最小值。 当k=n时，相当于找最大值。 当k=n/2时，称中值。;（1）若k=s，则rs就是第k小元素； （2）若ks，则第k小元素一定在序列ri ～ rs-1中； （3）若ks，则第k小元素一定在序列rs+1 ～ rj中； 无论哪种情况，或者已经得出结果（如果轴值恰好是序列的中值），或者将选择问题的查找区间减少一半。;选择问题的例子 ;A[1…28]={8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7,61,36,9}，求A的中位数元素，即第14小元素。(k=14);{11,25,33,14,23,22,13,16,12,17,29,32};算法——选择问题 1. i=1; j=