递归和归纳法课件.ppt

1、（1）递归递归递归是一种十分重要的程序设计方法，对于一些问题，用递归方法设计算法可使算法简洁明了，逻辑清晰，易于设计。n递归递归指算法自己调用自己,相应的算法称为递归算法递归算法。n递归分类：递归分类：直接递归与间接递归n递归方法：递归方法：解决一类满足递归关系的问题。n递归本质：递归本质：对原问题的求解可转化为对其性质相同的子问题的求解。基于归纳的递归算法基于归纳的递归算法(递归概念递归概念)基于归纳的递归算法基于归纳的递归算法(递归概念递归概念)例子：计算阶乘函数)!1(nn!n!n0n0n1算法算法 计算阶乘函数 输入：输入：输出：输出：过程：过程：1if n=0 then return

2、 12 else return n*fatorial(n-1)!nnn递归关系递归关系(特性特性)：产生递归的基础。n递归出口递归出口(结束条件结束条件)：确定递归的层数。n参数设置：参数设置：参数表示了原问题及其不同的子问题。)(nfactorial!n基于归纳的递归算法基于归纳的递归算法(归纳的思想方法归纳的思想方法)（2）归纳法的思想方法归纳法的思想方法 对于一个规模为n的问题p(n)，归纳法的思想方法是：n基础步：a1是问题p(1)的解。n归纳步：对所有的k，1kn，若b是问题p(k)的解，则p(b)是问题p(k+1)的解。其中，p(b)是对问题的某种运算或处理。例如。因为a1是问题p

3、(1)的解，若a2=p(a1)，a2是问题p(2)的解；以此类推，an-1是问题p(n-1)的解，且an=p(an-1)，则an是问题p(n)的解。因此，求解问题p(n)的解an，可先求问题p(n-1)的解an-1，然后再对an-1进行p运算或处理。为求问题p(n-1)的解，先求问题p(n-2)的解，如此不断进行递归求解。直至p(1)为止。当得到p(1)的解之后，再返回来，不断地把所得的解进行p运算或处理，直至p(n)的解为止。这就是基于归纳的递归算法的思想方法。基于归纳的递归算法基于归纳的递归算法(选择排序)例5.1 基于递归的选择排序 假定要对n个元素的数组A进行排序，可以如下进行：n基础

4、步：当n=1时，数组A2n的最小者Aj，Aj与A1交换，A1有排序。n归纳步：如果A1n-1的n-1个元素已经排序，则An有序。算法算法5.1 SelectionSort 输入：输入：n个元素的数组A1n 输出：输出：按非降序排列数组A1n 1.sort(1)过程 sort(i)1 if in then 2 k=i基于归纳的递归算法基于归纳的递归算法(选择排序)3 for j=i+1 to n 4 if Aj1 then2x=Ai3sort(i-1)基于归纳的递归算法基于归纳的递归算法(插入排序)3j=i-1 4 while j0 and Ajx 5Aj+1Aj 6 j=j+1 7 end w

5、hile 8Aj+1=x 9 end if 最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析:由基础步知：当n=1时，即只有一个元素已经有序，元素比较次数为0；当n1时，可由归纳步知，总比较次数C(n)为：)(nC10n1)1()1(nnnC)()1()1()(2211nnnnjjnCnjnj基于归纳的递归算法基于归纳的递归算法(整数幂)0,10,2222mxmmxxmxxmmmm为奇数为偶数例5.3 整数幂 用一个高效的方法求实数x的n次幂，其高效算法描述如下：算法算法 Exprec输入：输入：实数x和非负整数n输出：输出：1.power(x,n)过程：power(x,m)nx基于归

6、纳的递归算法基于归纳的递归算法(整数幂)1 if m=0 then y=12 else3 y=power(x,m/2)4 y=y25 if m为奇数 then y=xy6 end if7 return y最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析:乘法次数C(n)为：)(nC00n022nnC)(log)(nnC例5.4 设有n阶多项式：Pn(x)=anxn+an-1xn-1+a1x+a0 则根据Horner规则，得 Pn(x)=(an)x+an-1)x+an-2)x+an-3)x)x+a1)x+a0Pn(x)=x Pn-1(x)+a0由归纳知：基于归纳的递归算法基于归纳的递归算

7、法(n阶多项式)n基础步：当n=0时，有P0(x)=an。n归纳步：对于任意的k，1kn，如果前面k-1步已计算出pk-1：Pk-1(x)=anxk-1+an-1xk-2+an-k+2x+an-k+1 则有：Pk(x)=x Pk-1(x)+an-k 算法算法 HORNERERC 输入：输入：非负正数n,实数序列a0,a1,an和实数x 输出：输出：n次多项式Pn(x)=anxn+an-1xn-1+a1x+a0的值 1 hn(n,x)过程过程 hn(m,x)1 if m=0 then 2 return an 3 else 4 p=x*hn(m-1,x)+an-m 5 return p 6 end

8、 if基于归纳的递归算法基于归纳的递归算法(n阶多项式)基于归纳的递归算法基于归纳的递归算法(n阶多项式)最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析:第4行中的乘法作为基本运算，总的乘法次数C(n)为：)(nC00n01)1(nnC)()(nnC空间复杂性算法分析空间复杂性算法分析：)()(nnS另外：另外：基于归纳的迭代算法参见课本算法5.6(P85)例5.5 求序列1，2，n的所有排列。假定序列已依次存放在数组A中，为了生成这n个元素的所有排列，可以采用下面步骤：(1)因A1=1，即排列的第一个元素为1，生成后面的n-1个元素的排列。(2)A1与A2互换，即排列的第一个元素为

9、2，生成后面的n-1个元素的排列。(3)如此下去，A1与An互换，即排列的第一个元素为n，生成后面的n-1个元素的排列。至此，为了生成后面n-1个元素的排列，继续采取下面的步骤：(1)因A2=2，即排列的第二个元素为2，生成后面的n-2个元素的排列。(2)A2与A3互换，即排列的第二个元素为3，生成后面的n-2个元素的排列。(3)如此下去，A2与An互换，即排列的第二个元素为n，生成后面的n-2个元素的排列。基于归纳的递归算法基于归纳的递归算法(排列)这种步骤继续，当排列的前n-2个元素已 确定后，为生成 后面2 个元素的排列，可以：(1)An-1=n-1，即排列的第n-1个元素为n-1，生成

10、后面的1个元素的排列。(2)An-1与An互换，即排列的第n-1个元素为n，生成后面的1 个元素的排列，此时A中的n个元素已构成一个排列。(3)如此下去，A2与An互换，即排列的第二个元素为n，生成后面的1个元素的排列，此时A中的n个元素已构成一个排列。由归纳法知：基于归纳的递归算法基于归纳的递归算法(排列)n基础步：当k=1时，数组只有一个元素，它已是一个排列。n归纳步：如果前面k-1个元素已是完成的排列，为了对后面的k个元素的排列，只要元素Ak与Aj逐一互换(k+1jn)，每互换一次，调用算法perm(k)即可完成一个排列。于是，n个元素的全排列算法如下：基于归纳的递归算法基于归纳的递归算

11、法(排列)算法算法 Permutation1 输入：输入：数组A1n，正数n 输出：输出：数1，2，n的所有可能排列 1 for j=1 to n 2 Aj=j 3 end for 过程过程 perm1(m)1 if m=n then 2 output A1n 3 else 4 for j=m to n 5 Am与Aj互换 6perm1(m+1)7Am与Aj互换 8end for 9end if 基于归纳的递归算法基于归纳的递归算法(排列)最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析:基本运算为迭代次数,第6行被调用n次，元素互换次数为2n次总的递归调用次数C(n)为：)(nC10

12、n12)1(nnnnC)!()(nnnC解得：另外：另外：第二种全排列算法参见课本算法5.8(P97)基于归纳的递归算法基于归纳的递归算法(寻找多数元素寻找多数元素)n寻找多数元素寻找多数元素 设A1n是一个整数序列和A中的元素a，如果a在A中出现的次数多于 n/2，则称a是A中的多数元素。如序列1，3，2，3，3，4，3中3是多数元素。那么，有哪些寻找多数元素的方法呢？寻找多数元素的方法：(1)蛮力方法：要花次 比较，才能确定A中是否有多数元素。(2)排序方法：最坏情况下，要花 次比较，才能确定A中是否有多数元素。(3)寻找中间元素方法：由课本6.5知，花次 比较，能确定A中是否有多数元素，

13、但它的常量太大，且方法复杂。综上所述，是否能用归纳法的思想，发现一个更好的寻找多数元素的方法，回答是肯定的。)(2n)log(nn)(n基于归纳的递归算法基于归纳的递归算法(寻找多数元素寻找多数元素)再次考察序列1，3，2，3，3，4，只比较9次就可以确定序列中的多数元素是3。n观察结论观察结论 在原序列中去除两个不同的元素后，那么在原序列中的多数元素还是多数元素。这个观察结论支持寻找多数元素的侯选者的过程。于是，在A1n寻找多数元素的侯选者的过程如下：(1)计数器置count=1，j=1，c=Aj。(2)重复直至j=n或count n/2 then return c 7 else retur

14、n none基于归纳的递归算法基于归纳的递归算法(寻找多数元素寻找多数元素)过程过程 candidate(m)1 j=m;c=Aj;count=1 2 while jn and count0 3j=j+1 4 if Aj=c then count=count+1 5 else count=count-1 6 end if 7 if j=n then return c 8 else return candidate(j+1)最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析 (1)在过程candidate的第7步，当j=n时，即c是侯选者，至多比较n-1次，而第八步递归0次；而算法MAJORITY中的第四步比较次数为n。所以，总比较次数C(n)=。(2)在过程candidate的第7步，当jn时，即count=0，c不是侯选者，而第八步至多递归n/2次；而算法MAJORITY中的第四步比较次数为n。所以，总比较次数C(n)=。综上所述，算法MAJORITY总比较次数C(n)=。)(n)(n)(n