递归和归纳法课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,（1）,递归,递归是一种十分重要的程序设计方法，对于一些问题，用递归方法设计算法可使算法简洁明了，逻辑清晰，易于设计。,递归,指算法自己调用自己, 相应的算法称为,递归算法,。,递归分类：,直接递归与间接递归,递归方法：,解决一类满足递归关系的问题。,递归本质：,对原问题的求解可转化为对其性质相同的子问题的求解。,基于归纳的递归算法(,递归概念,),1,基于归纳的递归算法(,递归概念,),例子：计算阶乘函数,算法,计算阶乘函数,输入：,输出：,过程：,1if n=0 then return 1,2 else return n*fatorial(n-1),递归关系,(,特性,),：,产生递归的基础。,递归出口,(,结束条件,),：,确定递归的层数。,参数设置：,参数表示了原问题及其不同的子问题。,2,基于归纳的递归算法(,归纳的思想方法,),（2）,归纳法的思想方法,对于一个规模为n的问题p(n)，归纳法的思想方法是：,基础步：,a,1,是问题,p(1),的解。,归纳步：对所有的,k，1,k,n，,若,b,是问题,p(k),的解，则,p(b),是问题,p(k+1),的解。其中，,p(b),是对问题的某种运算或处理。,例如。因为a,1,是问题p(1)的解，若a,2,=p(a,1,)， a,2,是问题p(2)的解；以此类推，a,n-1,是问题p(n-1)的解，且a,n,=p(a,n-1,)， 则a,n,是问题p(n)的解。 因此，求解问题p(n)的解a,n,，可先求问题p(n-1)的解a,n-1,，然后再对a,n-1,进行p运算或处理。为求问题p(n-1)的解，先求问题p(n-2)的解，如此不断进行递归求解。直至p(1)为止。当得到p(1)的解之后，再返回来，不断地把所得的解进行p运算或处理，直至p(n)的解为止。这就是基于归纳的递归算法的思想方法。,3,基于归纳的递归算法(,选择排序,),例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 then,2 k=i,4,基于归纳的递归算法(,选择排序,),3 for j=i+1 to n,4 if Aj1 then,2x=Ai,3sort(i-1),6,基于归纳的递归算法(,插入,排序,),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)为：,7,基于归纳的递归算法(,整数幂,),例,5.3,整数幂,用一个高效的方法求实数x的n次幂，其高效算法描述如下：,算法,Exprec,输入：,实数x和非负整数n,输出：,1. power(x,n),过程：power(x,m),8,基于归纳的递归算法(,整数幂,),if m=0 then y=1,else,y=power(x,m/2,),y=y,2,if m,为奇数,then y=,xy,end if,7 return y,最坏情况下时间复杂性算法分析,:,乘法次数C(n)为：,9,例,5.4,设有n阶多项式：,P,n,(x)=a,n,x,n,+ a,n-1,x,n-1,+ a,1,x + a,0,则根据Horner规则，得,P,n,(x)=(a,n,)x+ a,n- 1,)x + a,n-2,)x + a,n-3,)x )x + a,1,),x+ a,0,P,n,(x)=x P,n-1,(x) + a,0,由归纳知：,基于归纳的递归算法(,n阶多项式,),基础步：当,n=0,时，有,P,0,(x)=a,n,。,归纳步：对于任意的,k，1,k,n ，,如果前面,k-1,步已计算出,p,k,-1：,P,k,-1,(x)=,a,n,x,k,-1,+ a,n-1,x,k-2,+ a,n-k+2,x + a,n-k+1,则有：,P,k,(x)=x,P,k,-1,(x)+ a,n-k,10,算法,HORNERERC,输入：,非负正数n, 实数序列a,0, a,1, a,n,和实数x,输出：,n次多项式P,n,(x)=a,n,x,n,+ a,n-1,x,n-1,+ a,1,x,+ a,0,的值,1 hn(n, x),过程 hn(m, x),1 if m=0 then,2 return a,n,3 else,4 p=x*hn(m-1, x)+ a,n-m,5,return p,6 end if,基于归纳的递归算法(,n阶多项式,),11,基于归纳的递归算法(,n阶多项式,),最坏情况下时间复杂性算法分析,:,第4行中的乘法作为基本运算，总的乘法次数C(n)为：,空间复杂性算法分析,：,另外：,基于归纳的迭代算法,参见课本算法5.6(P85),12,例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个元素的排列，继续采取下面的步骤：,(1) 因A2=2，即排列的第二个元素为2，生成后面的n-2个元素的排列。,(2) A2与A3互换，即排列的第二个元素为3，生成后面的n-2个元素的排列。,(3)如此下去， A2与An互换，即排列的第二个元素为n，生成后面的n-2个元素的排列。,基于归纳的递归算法(,排列,),13,这种步骤继续，当排列的前n-2个元素已 确定后，为生成 后面2 个元素的排列，可以：,(1) An-1=n-1，即排列的第n-1个元素为n-1，生成后面的1个元素的排列。,(2) An-1与An互换，即排列的第n-1个元素为n，生成后面的1 个元素的排列，此时A中的n个元素已构成一个排列。,(3)如此下去， A2与An互换，即排列的第二个元素为n，生成后面的1个元素的排列，此时A中的n个元素已构成一个排列。,由归纳法知：,基于归纳的递归算法(,排列,),基础步：当,k=1,时，数组只有一个元素，它已是一个排列,。,归纳步：如果前面,k-1,个元素已是完成的排列,，,为了对后面的,k,个元素的排列，只要元素,Ak,与,Aj,逐一互换(,k+1,j,n)，,每互换一次，调用算法,perm(k),即可完成一个排列。,于是，,n,个元素的全排列算法如下：,14,基于归纳的递归算法(,排列,),算法 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,15,基于归纳的递归算法(,排列,),最坏情况下时间复杂性算法分析,:,基本运算为迭代次数,第6行被调用n次，元素互换次数为2n次总的递归调用次数C(n)为：,解得,：,另外：,第二种全排列算法参见课本算法5.8(P97),16,基于归纳的递归算法(,寻找多数元素,),寻找多数元素,设A1,n是一个整数序列和A中的元素a，如果a在A中出现的次数多于,n/2,，则称a是A中的多数元素。,如序列1，3，2，3，3，4，3中3是多数元素。那么，有哪些寻找多数元素的方法呢？,寻找多数元素的方法：,(1)蛮力方法：要花次 比较，才能确定A中是否有多数元素。,(2)排序方法：最坏情况下，要花 次比较 ，才能确定A中是否有多数元素。,(3)寻找中间元素方法：由课本6.5知，花次 比较，能确定A中是否有多数元素，但它的常量太大，且方法复杂。,综上所述，是否能用归纳法的思想，发现一个更好的寻找多数元素的方法，回答是肯定的。,17,基于归纳的递归算法(,寻找多数元素,),再次考察序列1，3，2，3，3，4，只比较9次就可以确定序列中的多数元素是3 。,观察结论,在原序列中去除两个不同的元素后，那么在原序列中的多数元素还是多数元素。,这个观察结论支持寻找多数元素的侯选者的过程。于是，在A1,n寻找多数元素的侯选者的过程如下：,(1)计数器置count=1，j=1，c=Aj。,(2)重复直至j=n或count ,n/2, then return c,7 else return none,19,基于归纳的递归算法(,寻找多数元素,),过程 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)= 。,20,