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

1、算法设计与分析 归纳法归纳法 主要内容： 介绍递归算法设计的基本要素和方法。 归纳法 一. 递归的概念和递归算法设计要素1递归的概念 递归是一种十分重要的程序设计方法，对于一些问题，用递归方法设计算法可使算法简洁明了，逻辑清晰，易于设计。递归指算法自己调用自己, 相应的算法称为递归算法。 直接递归与间接递归递归方法用于解决一类满足递归关系的问题。递归关系：对原问题的求解可转化为对其性质相同 的子问题的求解。归纳法 一. 递归的概念和递归算法设计要素1递归的概念例：多项式求值的Horner规则 （5.5 P94） Pn(x)=anxn + an-1xn-1 + a1x + a0 Horner规则

2、： 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)=x Pn-1(x) + a0 从而将求Pn(x)的值的问题转化为求Pn-1(x)的值的问题。归纳法 一. 递归的概念和递归算法设计要素1递归的概念 一般的有： Pm(x) = x Pm-1(x) + an-m , m=1, 2, ,

3、n P0(x) = an 其中，Pm(x)=anxm + an-1xm-1 + an-m+1x + an-m 。 求Pn(x)的值的递归算法：算法 HORNERERC 求Pn(x)的值的迭代算法：算法5.6 HORNER（P95）归纳法 一. 递归的概念和递归算法设计要素1递归的概念递归算法与迭代算法递归算法中所蕴含的归纳法思想归纳法 一. 递归的概念和递归算法设计要素2递归算法设计要素 递归关系（特性）：产生递归的基础。 当算法中某步骤要通过解性质相同的子问题实现时，该步骤用递归调用实现。 递归出口（结束条件）：确定递归的层数。 当子问题的规模充分小时可直接求解时，递归结束。归纳法 一. 递

4、归的概念和递归算法设计要素2递归算法设计要素 参数设置：参数表示了原问题及其不同的子问题。 参数表示了子问题的大小和状态，以区别原问题以及不同层次的子问题。算法功能的设定：严格规定递归算法要解决什么样的问题。 算法功能的正确设定是保证递归过程正确进行的前提。 例：多项式求值 注意： 初始化，递归与循环，算法正确性的验证，归纳法 二.简单的递归算法设计之例 1选择排序与插入排序 ( 5.2 P90 ) 设对n个数据升序排序。(1)选择排序 基本思想： 递归关系：当选出最小元素并交换到第一个位置上后， 问题转换为对其余元素的排序。 递归出口：当只剩下一个元素时，自然有序。 参数：待排序子序列的起始

5、位置。 功能：对待排序子序列按升序选择排序。 选择排序递归算法：选择排序算法 (P90 算法5.1) 归纳法 二.简单的递归算法设计之例 1选择排序与插入排序 ( 5.2 P90 ) (2) 插入排序 基本思想： 递归关系：若前n-1个元素组成的子序列为有序的，则将第n个元素插入到前面的有序子序列中就可完成对n个元素的排序。问题转换为对前n-1个元素组成的子序列的插入排序问题。 递归出口：长度为1的子序列自然有序。 参数：待排序子序列的终止位置。 功能：对待排序子序列按升序插入排序。 插入排序递归算法：插入排序算法 (P91算法5.2) 递归算法中递归调用的位置归纳法 二.简单的递归算法设计之

6、例 2整数幂问题 (5.4 P93) 问题描述：求实数x的n次幂（n为非负整数）。递归关系及递归出口： 例：x9=x( x4)2 x4=( x2)2 参数：m, x。 算法：算法 5.4 EXPERC归纳法 三. 递归算法设计之例 1棋子移动游戏 问题描述：有2n（n=4为整数）棋子，黑白棋子各n个，初始 状态为： _ _ （右边有两个空位） 终止状态为： _ _ （左边有两个空位） 将棋子从初始状态移动成终止状态。移动规则如下： 1) 每次必须同时移动相邻两个棋子； 2) 移动方向不限； 3) 每次移动必须跳过若干棋子。 归纳法 三. 递归算法设计之例 1棋子移动游戏 递归关系： 当n=5时

7、，经过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=A1UA2UUAn 记Bi为a1 , ai-1, ai+1, an的所有排列组成 的集合，i=1, 2, n, 则 Ai=Bi中的排列前加ai 归纳法 三. 递归算法设计之例 2生成

8、全排列 （5.6） 递归关系：求解n个元素的全排列问题可转化为求解n个n-1个元素的全排列问题（即要求A只要求B1 , B2, Bn）。递归出口：求一个元素的全排列。参数：指定当前需要求全排列的子序列的位置。算法：算法及其时间复杂性 归纳法 三. 递归算法设计之例 3寻找多数元素 （5.7 P98） 问题描述：求n个元素序列中的多数元素，多数元素为在序列中出现的次数多于n/2的元素。 一个序列不一定存在多数元素。 一个序列的多数元素若存在则唯一。归纳法 三. 递归算法设计之例 3寻找多数元素 （5.7 P98） 有关方法： 蛮力方法：计数每个元素在序列中的出现次数。 时间复杂性：(n2)。 蛮

9、力方法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。 排序方法：先对序列排序，然后扫描排序结果序列，求序列中的出现次数最多的元素。 时间复杂性：(nlogn)。归纳法 三. 递归算法设计之例 3寻找多数元素 （5.7 P98） 有关方法： 求中间元素方法：先求序列的中间元素，然后判断中间元素是否为多数元素。 时间复杂性：(n)。 中间元素为序列中的第 小元素，多数元素一定是中间元素，求中间元素的分治算法时间复杂性为(n)，但其中的常系数较大。归纳法 三. 递归算法设计之例 3寻找多数元素 （5.7 P98） 一种更高效的方法： 观察结论5.1：在原序列中除去两个不同

10、元素后，原序列中的多数元素在新序列中还是多数元素。 思考：观察结论5.1的逆命题是否成立？ 推论：在原序列中除去多对不同元素后，原序列中的多数元素在新序列中还是多数元素。归纳法 三. 递归算法设计之例 3寻找多数元素 （5.7 P98） 递归关系： 通过对除去多对不同元素后的子序列的多数元素问题的求解可得到原序列的多数元素问题的候选解。 注意：子序列的多数元素只是原序列的候选多数元素，必须验证。但若子序列不存在多数元素，则原序列就一定不存在多数元素。 归纳法 三. 递归算法设计之例 3寻找多数元素 （5.7 P98） 算法的基本思想：逐个扫描序列元素，不断除去不同的元素对，得到新的子序列，对子序列做同样的运算，直至序列扫描完毕。递归出口：序列已扫描完。参数：待扫描的子序列的起始位置。算法：寻找多数元素.doc 归纳法 递归算法设计