算法设计与分析-第5章归纳法.ppt

算法设计与分析 归纳法 归纳法 主要内容 介绍递归算法设计的基本要素和方法 归纳法 一 递归的概念和递归算法设计要素1 递归的概念递归是一种十分重要的程序设计方法 对于一些问题 用递归方法设计算法可使算法简洁明了 逻辑清晰 易于设计 递归指算法自己调用自己 相应的算法称为递归算法 直接递归与间接递归递归方法用于解决一类满足递归关系的问题 递归关系 对原问题的求解可转化为对其性质相同的子问题的求解 归纳法 一 递归的概念和递归算法设计要素1 递归的概念例 多项式求值的Horner规则 5 5P94 Pn x anxn an 1xn 1 a1x a0Horner规则 Pn x anx an 1 x an 2 x an 3 x a1 x a0 归纳法 一 递归的概念和递归算法设计要素1 递归的概念令Pn 1 x anxn 1 an 1xn 2 a2x a1则根据Horner规则 Pn 1 x anx an 1 x an 2 x an 3 x a1于是有Pn x xPn 1 x a0从而将求Pn x 的值的问题转化为求Pn 1 x 的值的问题 归纳法 一 递归的概念和递归算法设计要素1 递归的概念一般的有 Pm x xPm 1 x an m m 1 2 nP0 x an其中 Pm x anxm an 1xm 1 an m 1x an m 求Pn x 的值的递归算法 算法HORNERERC求Pn x 的值的迭代算法 算法5 6HORNER P95 归纳法 一 递归的概念和递归算法设计要素1 递归的概念递归算法与迭代算法递归算法中所蕴含的归纳法思想 归纳法 一 递归的概念和递归算法设计要素2 递归算法设计要素递归关系 特性 产生递归的基础 当算法中某步骤要通过解性质相同的子问题实现时 该步骤用递归调用实现 递归出口 结束条件 确定递归的层数 当子问题的规模充分小时可直接求解时 递归结束 归纳法 一 递归的概念和递归算法设计要素2 递归算法设计要素参数设置 参数表示了原问题及其不同的子问题 参数表示了子问题的大小和状态 以区别原问题以及不同层次的子问题 算法功能的设定 严格规定递归算法要解决什么样的问题 算法功能的正确设定是保证递归过程正确进行的前提 例 多项式求值注意 初始化 递归与循环 算法正确性的验证 归纳法 二 简单的递归算法设计之例1 选择排序与插入排序 5 2P90 设对n个数据升序排序 1 选择排序 基本思想 递归关系 当选出最小元素并交换到第一个位置上后 问题转换为对其余元素的排序 递归出口 当只剩下一个元素时 自然有序 参数 待排序子序列的起始位置 功能 对待排序子序列按升序选择排序 选择排序递归算法 选择排序算法 P90算法5 1 归纳法 二 简单的递归算法设计之例1 选择排序与插入排序 5 2P90 2 插入排序 基本思想 递归关系 若前n 1个元素组成的子序列为有序的 则将第n个元素插入到前面的有序子序列中就可完成对n个元素的排序 问题转换为对前n 1个元素组成的子序列的插入排序问题 递归出口 长度为1的子序列自然有序 参数 待排序子序列的终止位置 功能 对待排序子序列按升序插入排序 插入排序递归算法 插入排序算法 P91算法5 2 递归算法中递归调用的位置 归纳法 二 简单的递归算法设计之例2 整数幂问题 5 4P93 问题描述 求实数x的n次幂 n为非负整数 递归关系及递归出口 例 x9 x x4 2x4 x2 2参数 m x 算法 算法5 4EXPERC 归纳法 三 递归算法设计之例1 棋子移动游戏问题描述 有2n n 4为整数 棋子 黑白棋子各n个 初始状态为 右边有两个空位 终止状态为 左边有两个空位 将棋子从初始状态移动成终止状态 移动规则如下 1 每次必须同时移动相邻两个棋子到空位 2 每次移动必须跳过若干棋子 归纳法 三 递归算法设计之例1 棋子移动游戏递归关系 当n 5时 经过2次移动 规模为n的问题可转化为规模为n 1的子问题 分析 棋子移动游戏 ppt递归出口 n 4参数 问题规模n算法 算法CHESS 归纳法 三 递归算法设计之例2 生成全排列 5 6 问题描述 生成n个互异元素a1 a2 an的全排列 所有排列 分析 记A为a1 a2 an的所有排列组成的集合 Ai为A中以ai开头的所有排列组成的集合 i 1 2 n 则Ai互不相交且A A1UA2U UAn记Bi为a1 ai 1 ai 1 an的所有排列组成的集合 i 1 2 n 则Ai Bi中的排列前加ai 归纳法 三 递归算法设计之例2 生成全排列 5 6 递归关系 求解n个元素的全排列问题可转化为求解n个n 1个元素的全排列问题 即要求A只要求B1 B2 Bn 递归出口 求一个元素的全排列 参数 指定当前需要求全排列的子序列的位置 算法 算法及其时间复杂性 归纳法 三 递归算法设计之例3 寻找多数元素 5 7P98 问题描述 求n个元素序列中的多数元素 多数元素为在序列中出现的次数多于n 2的元素 一个序列不一定存在多数元素 一个序列的多数元素若存在则唯一 归纳法 三 递归算法设计之例3 寻找多数元素 5 7P98 有关方法 蛮力方法 计数每个元素在序列中的出现次数 时间复杂性 n2 蛮力方法是一种简单直接地解决问题的方法 常常直接基于问题的描述和所涉及的概念定义 排序方法 先对序列排序 然后扫描排序结果序列 求序列中的出现次数最多的元素 时间复杂性 nlogn 中间元素为序列中的第小元素 多数元素一定是中间元素 求中间元素的分治算法时间复杂性为 n 但其中的常系数较大 归纳法 三 递归算法设计之例3 寻找多数元素 5 7P98 有关方法 求中间元素方法 先求序列的中间元素 然后判断中间元素是否为多数元素 时间复杂性 n 归纳法 三 递归算法设计之例3 寻找多数元素 5 7P98 一种更高效的方法 观察结论5 1 在原序列中除去两个不同元素后 原序列中的多数元素在新序列中还是多数元素 思考 观察结论5 1的逆命题是否成立 推论 在原序列中除去多对不同元素后 原序列中的多数元素在新序列中还是多数元素 归纳法 三 递归算法设计之例3 寻找多数元素 5 7P98 递归关系 通过对除去多对不同元素后的子序列的多数元素问题的求解可得到原序列的多数元素问题的候选解 注意 子序列的多数元素只是原序列的候选多数元素 必须验证 但若子序列不存在多数元素 则原序列就一定不存在多数元素 归纳法 三 递归算法设计之例3 寻找多数元素 5 7P98 算法的基本思想 逐个扫描序列元素 不断除去不同的元素对 得到新的子序列 对子序列做同样的运算 直至序列扫描完毕 递归出口 序列已扫描完