《递归和归纳法课件》由会员分享，可在线阅读，更多相关《递归和归纳法课件（20页珍藏版）》请在金锄头文库上搜索。
1、（1）递归递归递归是一种十分重要的程序设计方法，对于一些问题，用递归方法设计算法可使算法简洁明了，逻辑清晰，易于设计。n递归递归指算法自己调用自己, 相应的算法称为递归算法递归算法。n递归分类：递归分类：直接递归与间接递归n递归方法：递归方法：解决一类满足递归关系的问题。n递归本质：递归本质：对原问题的求解可转化为对其性质相同的子问题的求解。 基于归纳的递归算法基于归纳的递归算法(递归概念递归概念)基于归纳的递归算法基于归纳的递归算法(递归概念递归概念)例子：计算阶乘函数 算法算法 计算阶乘函数 输入：输入：输出：输出：过程：过程：1if n=0 then return 12 else ret
2、urn n*fatorial(n-1)n递归关系递归关系(特性特性)：产生递归的基础。n递归出口递归出口(结束条件结束条件)：确定递归的层数。n参数设置：参数设置：参数表示了原问题及其不同的子问题。基于归纳的递归算法基于归纳的递归算法(归纳的思想方法归纳的思想方法)（2）归纳法的思想方法归纳法的思想方法 对于一个规模为n的问题p(n)，归纳法的思想方法是：n基础步：a1是问题p(1)的解。n归纳步：对所有的k，1kn，若b是问题p(k)的解，则p(b)是问题p(k+1)的解。其中， p(b)是对问题的某种运算或处理。 例如。因为a1是问题p(1)的解，若a2=p(a1)， a2是问题p(2)的
3、解；以此类推，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基础步：当n=1时，数组A2n的最小者Aj，A
4、j与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 while 8Aj+1=x 9
5、end if 最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析: 由基础步知：当n=1时，即只有一个元素已经有序，元素比较次数为0；当n1时，可由归纳步知，总比较次数C(n)为：基于归纳的递归算法基于归纳的递归算法(整数幂)例5.3 整数幂 用一个高效的方法求实数x的n次幂，其高效算法描述如下： 算法算法 Exprec输入：输入：实数x和非负整数n输出：输出：1. power(x,n)过程：power(x,m)基于归纳的递归算法基于归纳的递归算法(整数幂)1 if m=0 then y=12 else3 y=power(x,m/2)4 y=y25 if m为奇数 then y=xy6
6、end if77 return y 最坏情况下时间复杂性算法分析最坏情况下时间复杂性算法分析: 乘法次数C(n)为：例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由归纳知： 基于归纳的递归算法基于归纳的递归算法(n阶多项式)n基础步：当n=0时，有P0(x)=an 。n归纳步：对于任意的k，1kn ，如果前面k-1步已计算出pk-1： Pk-1(x)=anxk-1+ an-
7、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 if基于归纳的递归算法基于归纳的递归算法(n阶多项式) 基于归纳的递归算法基于归纳的递归算法(n阶多项式)最坏情况下
8、时间复杂性算法分析最坏情况下时间复杂性算法分析: 第4行中的乘法作为基本运算，总的乘法次数C(n)为：空空间间复复杂杂性性算算法法分分析析：另外：另外：基于归纳的迭代算法参见课本算法5.6(P85)例5.5 求序列1，2，n的所有排列。假定序列已依次存放在数组A中，为了生成这n个元素的所有排列，可以采用下面步骤： (1) 因A1=1，即排列的第一个元素为1，生成后面的n-1个元素的排列。(2) A1与A2互换，即排列的第一个元素为2，生成后面的n-1个元素的排列。(3)如此下去， A1与An互换，即排列的第一个元素为n，生成后面的n-1个元素的排列。至此，为了生成后面n-1个元素的排列，继续采
9、取下面的步骤： (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，生成后面的1个元素的排列。(2) An-1与An互换，即排列的第n-1个元素为n，生成后面的1 个元素的排列，此时A中的n个元素已构成一个排列。(3)如此下
10、去， A2与An互换，即排列的第二个元素为n，生成后面的1个元素的排列，此时A中的n个元素已构成一个排列。由归纳法知：基于归纳的递归算法基于归纳的递归算法(排列)n基础步：当k=1时，数组只有一个元素，它已是一个排列。n归纳步：如果前面k-1个元素已是完成的排列，为了对后面的k个元素的排列，只要元素Ak与Aj逐一互换(k+1jn)，每互换一次，调用算法perm(k)即可完成一个排列。于是，n个元素的全排列算法如下：基于归纳的递归算法基于归纳的递归算法(排列) 算法算法 Permutation1 输入：输入：数组A1n ，正数n 输出：输出：数1，2，n的所有可能排列 1 for j=1 to
11、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)为：解得：另外：另外：第二种全排列算法参见课本算法5.8(P97)基于归纳的递归算法基于归纳的递归算法(寻找多数元素寻找多数元素)n寻找多数元素寻找多数元
12、素 设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、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 return none基于归纳的递归算法基于归纳的递归算法(寻找多数元素寻找多数元素) 过程过程 candidate(m) 1 j=m;c=Aj;count=1 2 while jn and count0 3j=j+1
14、 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)= 。
