图问题中的流塑法筛选法调整堆立论问题.ppt

8 2图问题中的流塑法 8 2 41筛选法调整堆立论问题 recursion 就是子程序 或函数 直接调用自己或通过一系列调用语句间接调用自己 是一种描述问题和解决问题的基本方法 有两个基本要素 确定到何时终止 大问题是如何分解为小问题的 8 2 41筛选法调整堆立论问题 调用函数和被调用函数是同一个函数 需要注意的是筛选法调整堆函数的调用层次 如果把调用筛选法调整堆函数的主函数称为第0层 进入函数后 首次筛选法调整堆调用自身称为第1层调用 从第i层筛选法调整堆调用自身称为第i 1层 反之 退出第i 1层调用应该返回第i层 采用图示方法描述筛选法调整堆函数的运行轨迹 从中可较直观地了解到各调用层次及其执行情况 一个筛选法调整堆函数的调用过程类似于多个函数的嵌套调用 只不过调用函数和被调用函数是同一个函数 为了保证筛选法调整堆函数的正确执行 系统需设立一个工作栈 具体地说 筛选法调整堆调用的内部执行过程如下 1 运行开始时 首先为筛选法调整堆调用建立一个工作栈 其结构包括值参 局部变量和返回地址 2 每次执行筛选法调整堆调用之前 把筛选法调整堆函数的值参和局部变量的当前值以及调用后的返回地址压栈 3 每次筛选法调整堆调用结束后 将栈顶元素出栈 使相应的值参和局部变量恢复为调用前的值 然后转向返回地址指定的位置继续执行 可读性强 而且容易用数学归纳法来证明算法的正确性 因此 它为设计算法和调试程序带来很大方便 是算法设计中的一种强有力的工具 但是 因为筛选法调整堆算法是一种自身调用自身的算法 随着筛选法调整堆深度的增加 工作栈所需要的空间增大 筛选法调整堆调用时的辅助操作增多 因此 筛选法调整堆算法的运行效率较低 问题描述 一个长度为n n 1 的升序序列s 处在第n 2个位置的数称为序列s的中位数 两个序列的中位数是他们所有元素的升序序列的中位数 现有两个等长升序序列a和b 试设计一个在时间和空间两方面都尽可能高效的算法 找出两个序列的中位数 规模为n的原问题的解与较小规模 通常是n 2 的子问题的解之间具有关系 1 原问题的解只存在于其中一个较小规模的子问题中 2 原问题的解与其中一个较小规模的解之间存在某种对应关系 由于原问题的解与较小规模的子问题的解之间存在这种关系 所以 只需求解其中一个较小规模的子问题就可以得到原问题的解 2019 12 20 例 计算an的值 应用层治技术得到如下计算方法 应用分治法得到an的计算方法是 o log2n o nlog2n 想法 分别求出两个序列的中位数 记为a和b 比较a和b 有下列三种情况 a b 则a即为两个序列的中位数 ab 则中位数只能出现在b和a之间 在序列a中舍弃a之后的元素得到序列a1 在序列b中舍弃b之前的元素得到序列b1 在a1和b1中分别求出中位数 重复上述过程 直到两个序列中只有一个元素 则较小者即为所求 基本思想 在有序表中 取中间记录作为比较对象 若给定值与中间记录的关键码相等 则查找成功 若给定值小于中间记录的关键码 则在中间记录的左半区继续查找 若给定值大于中间记录的关键码 则在中间记录的右半区继续查找 不断重复上述过程 直到查找成功 或所查找的区域无记录 查找失败 2019 12 20 page11 判定树 长度为n的判定树的构造方法为 1 当n 0时 判定树为空 2 当n 0时 判定树的根结点是有序表中序号为mid