递归和归纳法课件.ppt

《递归和归纳法课件.ppt》由会员分享，可在线阅读，更多相关《递归和归纳法课件.ppt（20页珍藏版）》请在三一办公上搜索。

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

2、表示了原问题及其不同的子问题。,基于归纳的递归算法(归纳的思想方法),（2）归纳法的思想方法 对于一个规模为n的问题p(n)，归纳法的思想方法是：基础步：a1是问题p(1)的解。归纳步：对所有的k，1kn，若b是问题p(k)的解，则p(b)是问题p(k+1)的解。其中，p(b)是对问题的某种运算或处理。,例如。因为a1是问题p(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)的

3、解，先求问题p(n-2)的解，如此不断进行递归求解。直至p(1)为止。当得到p(1)的解之后，再返回来，不断地把所得的解进行p运算或处理，直至p(n)的解为止。这就是基于归纳的递归算法的思想方法。,基于归纳的递归算法(选择排序),例5.1 基于递归的选择排序 假定要对n个元素的数组A进行排序，可以如下进行：,基础步：当n=1时，数组A2n的最小者Aj，Aj与A1交换，A1有排序。归纳步：如果A1n-1的n-1个元素已经排序，则An有序。,算法5.1 SelectionSort 输入：n个元素的数组A1n 输出：按非降序排列数组A1n 1.sort(1)过程 sort(i)1 if in the

4、n 2 k=i,基于归纳的递归算法(选择排序),3 for j=i+1 to n 4 if AjAk then 5 k=j 6 end for 7 if ki then 互换Ai和Ak 8 sort(i+1)9 end if,最坏情况下时间复杂性算法分析:由基础步知：当n=1时，A1要有序，元素比较次数为n-1；当A1n-1已经排序，即前n-1个元素有序时，An自然有序。可由归纳步知，总比较次数C(n)为：,基于归纳的递归算法(插入排序),例5.2 基于递归的插入排序 假定要对n个元素的数组A进行排序，可以如下进行：,基础步：当n=1时，数组只有一个元素，它已排序。归纳步：如果前面k-1个元素

5、已经排序，只要对第k个元素逐一与前面的k-1个元素比较，把它插入适当位置，即可完成k个元素的排序。,算法 InsertionSort输入：n个元素的数组A1n输出：按非降序排列数组A1n1.sort(n)过程：sort(i)1if i1 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 end if,最坏情况下时间复杂性算法分析:由基础步知：当n=1时，即只有一个元素已经有序，元素比较次数为0；当n1时，可由归纳步知，总比较次数C(n)为：,基于

6、归纳的递归算法(整数幂),例5.3 整数幂 用一个高效的方法求实数x的n次幂，其高效算法描述如下：,算法 Exprec输入：实数x和非负整数n输出：1.power(x,n)过程：power(x,m),基于归纳的递归算法(整数幂),if m=0 then y=1 else y=power(x,m/2)y=y2 if m为奇数 then y=xy end if7 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

7、)x)x+a1)x+a0Pn(x)=x Pn-1(x)+a0由归纳知：,基于归纳的递归算法(n阶多项式),基础步：当n=0时，有P0(x)=an。归纳步：对于任意的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=

8、x*hn(m-1,x)+an-m 5 return p 6 end if,基于归纳的递归算法(n阶多项式),基于归纳的递归算法(n阶多项式),最坏情况下时间复杂性算法分析:第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互换，即

9、排列的第一个元素为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，生成后面的1个元素的排列。(2)An-1与An互换，即排列的第n-1个元素为n，生成后

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

11、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)为：,解得：,另外：第二种全排列算法参见课本算法5.8(P97),基于归纳的递归算法(寻找多数元素),寻找多数元素 设A1n是一个整数序列和A中的元素a，如果a在A中出现的次数多于 n/2，则称

12、a是A中的多数元素。如序列1，3，2，3，3，4，3中3是多数元素。那么，有哪些寻找多数元素的方法呢？寻找多数元素的方法：(1)蛮力方法：要花次 比较，才能确定A中是否有多数元素。(2)排序方法：最坏情况下，要花 次比较，才能确定A中是否有多数元素。(3)寻找中间元素方法：由课本6.5知，花次 比较，能确定A中是否有多数元素，但它的常量太大，且方法复杂。综上所述，是否能用归纳法的思想，发现一个更好的寻找多数元素的方法，回答是肯定的。,基于归纳的递归算法(寻找多数元素),再次考察序列1，3，2，3，3，4，只比较9次就可以确定序列中的多数元素是3。观察结论 在原序列中去除两个不同的元素后，那么在

13、原序列中的多数元素还是多数元素。这个观察结论支持寻找多数元素的侯选者的过程。于是，在A1n寻找多数元素的侯选者的过程如下：(1)计数器置count=1，j=1，c=Aj。(2)重复直至j=n或count=0(3)j=j+1;(4)若c=Aj，则count增1；否则count减1(5)重复结束(6)若j=n，则c是侯选者；否则重复在 Aj+1n寻找多数元 素的侯选者的过程,基于归纳的递归算法(寻找多数元素),所以有如下的寻找多数元素侯选者的过程candidate及确认多数元素算法MAJORITY,算法 MAJORITY 输入：n个元素数组A1n 输出：若有多数元素，则输出；否则输出none 1

14、c=candidate(1)2 count=0 3 for j=1 to n 4if Aj=c then count=count+1 5 end for 6 if 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 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)=。,