chap23递推关系举例、fibonacci数列

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,例1,Hanoi塔,问题：,这是组合数学中的一个著名问题。,n,个圆盘依其半径大小，从下而上套在,A,柱上。每次只允许取一个移到柱,B,或,C,上，而且不允许大盘放在小盘上方。若要求把柱A上的,n,个盘移到,C,柱上,请设计一种方法并估计要移动几个盘次。现在只有,A、B、C,三根柱子可用。,2.6 递推关系,1,Hanoi,问题是个典型的组合问题,第一步要设计,算法，进而估计它的复杂性，即估计工作量。,A B C,2.6 递推关系,算法：,n,=2时,第一步先把最上面的一个圆盘套在B上, ,第二步把下面的一个圆盘移到,C,上, ,最后把B上的圆盘移到C上,到此转移完毕,2,对于一般,n,个圆盘的问题，,假定,n,-1个盘子的转移算法已经确定。,先把上面的,n,-1,个圆盘经过C转移到B。,第二步把A下面一个圆盘移到C上,最后再把B上的,n,-1,个圆盘经过A转移到C上,A B C,2.6 递推关系,3,上述算法是递归的运用。,n,=2时已给出算法；,n,=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。,n,=4，5，依此类推。,2.6 递推关系,4,算法分析：,令,h,(,n,)表示,n,个圆盘所需要的转移盘次。根据算法先把前面,n,-1个盘子转移到B上；然后把第,n,个盘子转到C上；最后再一次将B上的,n,-1个盘子转移到C上。,n,=2时，算法是对的，因此，,n,=3是算法是对的。依此类推。于是有,2.6 递推关系,5,算法复杂度为：,H,(,x,)是序列,h,(1),h,(2),h,(3),的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。,当然，利用递推关系(a)式也可以依次求得,h,(1),h,(2),h,(3),，这样的连锁反应关系，叫做,递推关系,。,2.6 递推关系,6,下面介绍如何从(a)式求得母函数,H,(,x,),的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。,2.6 递推关系,7,根据,(a)，,或利用递推关系,(a),有,2.6 递推关系,8,整理得,这两种做法得到的结果是一样的。即：,2.6 递推关系,9,令,如何从母函数得到序列,h,(1),h,(2),h,(3),？,下面介绍一种化为,部分分数,的算法。,2.6 递推关系,10,由上式可得：,即：,2.6 递推关系,11,因为：,2.6 递推关系,12,例,2.,求,n,位十进制数中出现偶数个5的数的个数。,解:先从分析,n,位十进制数出现偶数个5的数的结构入手,p,1,p,2,p,n,-1,是,n,-1位十进制数，若含有偶数个5，则,p,n,取5以外的,0,1,2,3,4,6,7,8,9,九个数中的一个，若,p,1,p,2,p,n,-1,只有奇数个5，则取,p,n,=,5，使,p,1,p,2,p,n,-1,p,n,成为出现偶数个5的十进制数。,2.6 递推关系,13,解法1：,令,a,n,=,n,位十进制数中出现偶数个5的数的个数，,b,n,=,n,位十进制数中出现奇数个5的数的个数,。,有：,2.6 递推关系,(b)是关于序列,a,n,和,b,n,的联立关系。,14,设序列,a,n, 的母函数为,A,(,x,)，序列,b,n,的母函数为,B,(,x,) 。,则有,2.6 递推关系,15,2.6 递推关系,16,又：,故得关于母函数,A,(,x,),和,B,(,x,),的联立方程组：,2.6 递推关系,17,2.6 递推关系,18,2.6 递推关系,19,解法二：,n-,1,位的十进制数的全体共 ,从中去掉含有偶数个5的数，余下的便是,n,-1位中含有奇数个5的数。故有：,2.6 递推关系,20,令,2.6 递推关系,21,2.6 递推关系,22,表示，其结果可能有以下两种情况。,例3：,从,n,个元素,中取,r,个进行允许重复,的组合。假定允许重复的组合数用,1),不出现某特定元素设为,a,1,，,其组合数为,相当于排除,a,1,后从,中,取,r,个做允许重复的组合。,2.6 递推关系,23,2）,至少出现一个,a,1,，,取组合数为,相当于从,中取,r,-1,个做允许重复的组合然后再加上一个,a,1,得从,n,个元素中取,r,个允许重复的组合。,依据加法原则可得：,因,故令,2.6 递推关系,24,递推关系(1)带有两个参数,n,和,r,。,2.6 递推关系,25,(2),式是关于,G,n,(,x,) 的递推关系，但系数 (1,-,x,) 不是常数。,2.6 递推关系,26,由二项式定理,可得,2.6 递推关系,27,Fibonacci,数列是递推关系的又一个典型问题，数列的本身有着许多应用。,问题：,有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了,n,个月后共有多少对兔子？,设满,n,个月时兔子对数为,F,n,其中当月新生兔数目设为,N,n,对。第,n,-1,个月留下的兔子数目设为,O,n,对。,2.6 递推关系-,Fibonacci数列,28,但,即第,n,-2,个月所产的兔子到第,n,个月都有繁殖能力了.,由递推关系,(1),式可依次得到,2.6 递推关系,29,设,2.6 递推关系,30,2.6 递推关系,31,2.6 递推关系,32,2.6 递推关系,33,其中,2.6 递推关系,34,趣味结论,2.6 递推关系,35,证明：,2.6 递推关系,36,证明：,2.6 递推关系,37,证明：,2.6 递推关系,38,2.6 递推关系,三分法：,特点：每次区间长度缩短1/3,缺点：上一步点的值下一步没有用到,39,2.6 递推关系,0.618方法：,将三分法中的2/3换成0.618,不妨假设区间为0,1，上一步取值点为,x,1-,x,。下一步假设保留了区间0,x,，则下一步的取值点为,。,为了充分利用上一次取值点的信息，因此要求,由此解得,x,约等于0.618。,40,2.6 递推关系,Fibonacci方法：,41,