《c语言-递推递归》由会员分享，可在线阅读，更多相关《c语言-递推递归（47页珍藏版）》请在金锄头文库上搜索。
1、2019/1/16,1,第二讲,基础算法,计算机科学与技术 陈叶芳,2019/1/16,2,目录,递推 递归 排序与检索,2019/1/16,3,递推,指一个序列u1,u2,u3,un-1,un，后面的每一项都能按公式由前面的一项或连续的几项推算出来，或者前面的每一项都能按公式由后面的一项或连续的几项推算出来。前者叫“顺推”，后者叫“逆推”。,递推关系可用它前面1项表示的叫一阶递推数列，可用它前面2项表示的叫二阶递推数列。,2019/1/16,4,有5人坐在一起，当问第5个人多少岁,他说比第4个人大2岁，问第4个人多少岁,他说比第3个人大2岁，依此下去，问第一个人多少岁，他说他10岁，最后求第
2、5个人多少岁？,如果所坐的不是5人而是n人，写出第n个人的年龄表达式。,递推,x,x+2,2019/1/16,5,显然可以得到如下公式:,化简后的公式: F(n)=10+(n-1)*2,2019/1/16,6,斐波那契级数-递推的经典问题,一对新生小兔，一个月后长成中兔，从第三个月开始长成大兔并每个月生一对小兔。按此规律，一年后共有多少对兔子。,2019/1/16,7,Fibnacci 数列,即：1、1、2、3、5、8、13、21、34,关键：确定问题的递归特性,关键：分析出递归公式,关键：分析出初始条件,2019/1/16,8,例-巧妙推算走楼梯,楼梯有n级台阶，如果一步走1级或2级，试问：
3、共有多少种不同的走法？,1,2,3,n,走上第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 (n2)；,2019/1/16,9,例-巧妙推算走楼梯,1,2,3,n,初始条件：u1=1；u2=2;,1、2、3、5、8、13、21、34、55,斐波那契序列,201
4、9/1/16,10,总结：递推求解的基本方法：,首先，确认：能否容易的得到简单情况的解？,然后，假设：规模为N-1的情况已经得到解决。,最后，重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。,2019/1/16,11,在2n的长方形方格中,用n个12的骨牌铺满方格, 例如n=3时,为23方格，骨牌的铺放方案有三种(如图), 输入n ,输出铺放方案的总数,思考题（NBU OJ 1196）：,2019/1/16,12,骨牌铺放,1、如果用一个骨牌直接覆盖最左边一列，则剩下的2(n-1)个方格有f(n-1)种铺法；,2、如果用两个骨牌横向覆盖，则
5、剩下的2(n-2)个方格有f(n-2)种铺法；,2(n-1),2(n-2),3、第1列没有其他铺法，因此，f(n)=f(n-1)+f(n-2)；,2019/1/16,13,某人给不同地址不同姓名的n位朋友写信，信笺、信封都分别写好了。请问：所有信笺、信封全都装错的情况有多少种？,伯努利装错信封问题,信封：A B C D E F 信笺：a b c d e f ,伯努利问题：求n个元素的排列，要求在排列中没有一个元素处于它应当占有的位置。,2019/1/16,14,伯努利装错信封问题,信封：A B C D E F 信笺：a b c d e f ,错误1： 信封：A B C D E F 信笺：b a
6、 (后n-2封也都装错),错误2： 信封：A B C D E F 信笺：b 非a (后n-2封也都装错),装错情况种数Sn-2,装错情况种数Sn-1,Sn= （n-1)(Sn-1+ Sn-2),2019/1/16,15,分析思路：,S1=0, 只1封信，不会装错,S4=3(S3+S2)=9,S3=2(S2+S1)=2, 3封信，a-B,b-C,c-A或a-C,c-B,b-A,S2=1, 2封信，互相装错,2019/1/16,16,得到如下递推公式：,基本形式：d1=0; d2=1 递归式：dn= (n-1)*( dn-1 + dn-2),这就是著名的错排公式,2019/1/16,17,递归,i
7、nt fact(int n) /*递归函数*/ int r; if(n=0) r=1; else r=n*fact(n-1); /*递归*/ return r; ,printf(“%d!=%dn“,5,fact(5);,2019/1/16,18,递归,fact(5) =5*fact(4),院长,设计递归程序的重点是给下级安排工作,2019/1/16,19,递归,int SearchBin(int *r,int k,int low,int high) /递归 if(rowhigh) return 0; /failed mid=(low+high)/2; if(k=rmid) return mid
8、; /success else if(krmid) return SearchBin(*r,k,mid+1,high); else return SearchBin(*r,k,low,mid-1); ,2019/1/16,20,递归,int func(int n) /*求斐波那契数列的第n个数*/ int result; if(n=1) result=1; else if(n=2) result=1; else result=func(n-1)+func(n-2); /*递归*/ return result; ,2019/1/16,21,递归,Hanoi（汉诺塔）问题：三根柱子A、B、C，其中
9、A柱上有64个大小不等的圆盘，并且大的在下，小的在上。要求把这64个圆盘从A柱移动到C柱上，每次只能移动一个圆盘，移动时可以借助B来进行，但在任何时候，任何柱上的圆盘都必须保持大盘在下，小盘在上。求移动的过程。,A,B,C,2019/1/16,22,递归,(1)假如只有一个盘子的话，可以直接将盘子从A柱移动到C柱，即AC。,A,B,C,2019/1/16,23,递归,(2)假如有两个盘子，则： AB AC BC,A,B,C,2019/1/16,24,递归,(3)假如有三个盘子，则情况开始复杂，移动顺序为： AC AB CB AC BA BC AC,A,B,C,2019/1/16,25,递归,当
10、有n个盘子需要移动时，通常的方法如下： （1）把A柱上n-1个盘子借助C柱移动到B柱上。只有这样，C柱才能为空，则A柱上的第n个盘子（最大的那个）才能直接移动到C柱上。 （2）将A柱上的剩下的第n个盘子移动到C柱上。这个盘子已最后到位，不需要再移动了。 （3）再将B柱上的n-1个盘子借助A柱移动到C柱。,A,B,C,2019/1/16,26,递归,void hanoi(int n,char A,char B,char C) /*借助B，把n个盘子从A移动到C*/ if(n=1) move(A,C); else hanoi(n-1,A,C,B); /*借助C，把n-1个盘子从A移动到B*/ mo
11、ve(A,C); /*把第n个盘子从A移动到C*/ hanoi(n-1,B,A,C); /*借助A，再把n-1个盘子从B移动到C*/ ,A,B,C,scanf(“%d“,2019/1/16,27,排序与检索,查找表:用于查找的数据集合,由同一类型数据元素构成.,2019/1/16,28,排序与查找,A B C Z,banana Basketball ,列表：同一类型的数据元素（或记录）构成的集合。可利用任何数据结构实现。 关键字 ：数据元素的某个数据项的值。 查找：根据给定的关键字，在特定列表中确定与与之相同的数据元素，并返回该数据元素在列表中的位置。,2019/1/16,29,顺序查找法,i
12、nt seqListn+1; /n号单元用作监视哨 int Order_Search(int array ,int n,int key) int i; arrayn=key; /设置监视哨，不用判断越界 for(i=0;arrayi!=key;i+) ; return (in?i:-1); /找不到为-1,找到则为0n-1的数值 ,1.每一步骤中省去了对是否越界的判断，如i1000时,可以节省一半以上的查找时间.,特点：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败为止。,特点：从前到后，或从后到前。,for(i=0;in;i+) if(arrayi=key) return i;
13、 return -1;,2019/1/16,30,顺序查找法,int seqListn+1; /0号单元用作监视哨 int Order_Search(int *array,int n,int key) r0=key; /设置监视哨，不用判断越界 for(i=n;arrayi!=key;i-) ; return i; /找不到为0,找到则为1n的数值 ,2019/1/16,31,折半查找法(二分查找）,A在心里想一个不超过1000的正整数, 由B来猜,请问可以在多少次以内猜到该数?,特点：利用元素间的次序关系（要求数据集合有序）。采用了分治策略。,2019/1/16,32,折半查找法,3 10
14、15 19 25 28 40 55 83,low,high,mid,要求:查找关键字为55的数据元素 (1) mid=(low+high)/2 (2)55rmid,则查找mid+1,high区间,既low=mid+1,mid=(low+high)/2,3 10 15 19 25 28 40 55 83,low,high,mid,二分查找(Binary Search),要求：要查找的列表是按关键字大小有序排列的。,2019/1/16,33,折半查找法,3 10 15 19 25 28 40 55 83,low,high,mid,要求:查找关键字为18的数据元素 (1) mid=(low+high
15、)/2 (2)18rmid,则查找low,mid-1区间,既high=mid-1,mid=(low+high)/2,3 10 15 19 25 28 40 55 83,low,high,mid,若出现lowhigh情况,则查找失败,2019/1/16,34,折半查找法,int SearchBin(int *r,int k) low=1;high=n; while(lowrmid) low=mid+1; else high=mid-1; return 0; /failed ,2019/1/16,35,折半查找法,int SearchBin(int *r,int k,int low,int high) /递归 if(rowhigh) return 0; /failed mid=(low+high)/2; if(k=rmid) return mid; /success else if(krmid) return SearchBin(*r,k,mid+1,
