C语言-递推递归.ppt

《C语言-递推递归.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二讲基础算法计算机科学与技术陈叶芳9/26/20211目录递推递归排序与检索9/26/20212递推指一个序列u1,u2,u3,…,un-1,un，后面的每一项都能按公式由前面的一项或连续的几项推算出来，或者前面的每一项都能按公式由后面的一项或连续的几项推算出来。前者叫“顺推”，后者叫“逆推”。递推关系可用它前面1项表示的叫一阶递推数列，可用它前面2项表示的叫二阶递推数列。9/26/20213有5人坐在一起，当问第5个人多少岁,他说比第4个人大2岁，问第4个人多少岁,他说比第3个人大2岁，依此下去，问第一个人多少岁，他说他10岁，最后求第5个人

2、多少岁？如果所坐的不是5人而是n人，写出第n个人的年龄表达式。递推xx+210…….9/26/20214显然可以得到如下公式:化简后的公式:F(n)=10+(n-1)*29/26/20215斐波那契级数-递推的经典问题一对新生小兔，一个月后长成中兔，从第三个月开始长成大兔并每个月生一对小兔。按此规律，一年后共有多少对兔子。第n个月大兔对数中兔对数小兔对数总对数100112010131012411135212563238753513…9/26/20216Fibnacci数列即：1、1、2、3、5、8、13、21、34…关键：确定问题的递归特性关键：

3、分析出递归公式关键：分析出初始条件9/26/20217例-巧妙推算走楼梯楼梯有n级台阶，如果一步走1级或2级，试问：共有多少种不同的走法？123n走上第1级台阶，只有“一步1级”1种走法，u1=1；走上第2级台阶，从平地起步，有“一步1级”走2步和“一步2级”走1步这两种走法，u2=2；走上第3级台阶，或者从台阶2“一步1级”走1步上来，或者从台阶1“一步2级”走1步上来，u3=u2+u1=2+1=3；走上第n级台阶，只能从第n-1级“一步1级”走1步上来，或者从第n-2级台阶“一步2级”走1步上来，un=un-1+un-2(n>2)；9/26/

4、20218例-巧妙推算走楼梯123n初始条件：u1=1；u2=2;1、2、3、5、8、13、21、34、55斐波那契序列9/26/20219总结：递推求解的基本方法：首先，确认：能否容易的得到简单情况的解？然后，假设：规模为N-1的情况已经得到解决。最后，重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。9/26/202110在2×n的长方形方格中,用n个1×2的骨牌铺满方格,例如n=3时,为2×3方格，骨牌的铺放方案有三种(如图),输入n,输出铺放方案的总数思考题（NBUOJ1196）：9/2

5、6/202111骨牌铺放1、如果用一个骨牌直接覆盖最左边一列，则剩下的2(n-1)个方格有f(n-1)种铺法；2、如果用两个骨牌横向覆盖，则剩下的2(n-2)个方格有f(n-2)种铺法；2(n-1)2(n-2)3、第1列没有其他铺法，因此，f(n)=f(n-1)+f(n-2)；9/26/202112某人给不同地址不同姓名的n位朋友写信，信笺、信封都分别写好了。请问：所有信笺、信封全都装错的情况有多少种？伯努利装错信封问题信封：ABCDEF…信笺：abcdef…伯努利问题：求n个元素的排列，要求在排列中没有一个元素处于它应当占有的位置。9/26/2

6、02113伯努利装错信封问题信封：ABCDEF…信笺：abcdef…错误1：信封：ABCDEF…信笺：ba(后n-2封也都装错)错误2：信封：ABCDEF…信笺：b非a(后n-2封也都装错)装错情况种数Sn-2装错情况种数Sn-1Sn=（n-1)(Sn-1+Sn-2)9/26/202114分析思路：S1=0,只1封信，不会装错S4=3(S3+S2)=9S3=2(S2+S1)=2,3封信，a->B,b->C,c->A或a->C,c->B,b->AS2=1,2封信，互相装错9/26/202115得到如下递推公式：基本形式：d[1]=0;d[2]=1

7、递归式：d[n]=(n-1)*(d[n-1]+d[n-2])这就是著名的错排公式9/26/202116递归intfact(intn)/*递归函数*/{intr;if(n==0)r=1;elser=n*fact(n-1);/*递归*/returnr;}printf("%d!=%d",5,fact(5));9/26/202117递归fact(5)=5*fact(4)院长fact(4)=4*fact(3)主任fact(3)=3*fact(2)教师fact(2)=2*fact(1)班长fact(1)=1*fact(0)班委fact(0)=1同学设计

8、递归程序的重点是给下级安排工作9/26/202118递归intSearchBin(int*r,intk,intlow,inthigh)/