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

算法设计与分析 ——归纳法 归纳法 主要内容： 介绍递归算法设计的基本要素和方法。 归纳法 一. 递归的概念和递归算法设计要素 1．递归的概念 递归是一种十分重要的程序设计方法，对于一些问题，用递归方法设计算法可使算法简洁明了，逻辑清晰，易于设计。 递归指算法自己调用自己, 相应的算法称为递归算法。 直接递归与间接递归 递归方法用于解决一类满足递归关系的问题。 递归关系：对原问题的求解可转化为对其性质相同的子问题的求解。 归纳法 一. 递归的概念和递归算法设计要素 1．递归的概念 例：多项式求值的Horner规则 （5.5 P94） Pn(x)=anxn + an-1xn-1 +…+ a1x + a0 Horner规则： 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, …, 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．递归算法设计要素 递归关系（特性）：产生递归的基础。 当算法中某步骤要通过解性质相同的子问题实现时，该步骤用递归调用实现。 递归出口（结束条件）：确定递归的层数。 当子问题的规模充分小时可直接求解时，递归结束。 归纳法 一. 递归的概念和递归算法设计要素 2．递归算法设计要素 参数设置：参数表示了原问题及其不同的子问题。 参数表示了子问题的大小和状态，以区别原问题以及不同层次的子问题。 算法功能的设定：严格规定递归算法要解决什么样的问题。 算法功能的正确设定是保证递归过程正确进行的前提。 例：多项式求值 注意： 初始化，递归与循环，算法正确性的验证，… 归纳法 二.简单的递归算法设计之例 1．选择排序与插入排序 ( 5.2 P90 ) 设对n个数据升序排序。 (1)选择排序 ●基本思想： ●递归关系：当选出最小元素并交换到第一个位置上后， 问题转换为对其余元素的排序。 ●递归出口：当只剩下一个元素时，自然有序。 ●参数：待排序子序列的起始位置。 ●功能：对待排序子序列按升序选择排序。 ●选择排序递归算法：选择排序算法 (P90 算法5.1) 归纳法 二.简单的递归算法设计之例 1．选择排序与插入排序 ( 5.2 P90 ) (2) 插入排序 ● 基本思想： ● 递归关系：若前n-1个元素组成的子序列为有序的，则将第n个元素插入到前面的有序子序列中就可完成对n个元素的排序。问题转换为对前n-1个元素组成的子序列的插入排序问题。 ● 递归出口：长度为1的子序列自然有序。 ● 参数：待排序子序列的终止位置。 ● 功能：对待排序子序列按升序插入排序。 ● 插入排序递归算法：插入排序算法 (P91算法5.2) ● 递归算法中递归调用的位置 归纳法 二.简单的递归算法设计之例 2．整数幂问题 (5.4 P93) 问题描述：求实数x的n次幂（n为非负整数）。 递归关系及递归出口： 归纳法 三. 递归算法设计之例