版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
递推关系和Fibonacci数列1.递推关系Hanoi塔问题:这是组合数学中的一个著名问题。n个圆盘依其半径大小,从下而上套在A柱上。每次只允许取一个移到柱B或C上,而且不允许大盘放在小盘上方。若要求把柱An个盘移到C柱上,请设计一种方法并估计要移动几个盘次。现在只有A、B、C三根柱子可用。首先要设计算法,进而估计它的复杂性,即估计工作量。当n=2时,第一步把A柱的小圆盘移到B柱;第二步把A柱的大圆盘移到C柱;A
B
C第三步把B柱的小圆盘移到C柱,即完成移动。假定n-1个盘子的转移算法已经确定,对于一般n个圆盘的问题,ABC首先把A柱上面的n-1个圆盘移到B柱;然后把A柱最下面的圆盘移到C柱;最后把B柱的n-1个圆盘移到C柱,即完成移动。令h(n)表示n个圆盘所需要的转移盘次。因此有:从这个递推关系式可以逐项递推得到所有的h(n)。根据算法先把前面n-1个盘子转移到B上;然后把第n个盘子转到C上;最后将B的n-1个盘子转移到C上。下面我们利用母函数来得到h(n)的通项表达式。假设序列h(n)对应的母函数为H(x),即因此有或者利用x2:x3:x4:+)同样可以得到:假设下面我们用幂级数展开的方法得到h(n).利用待定系数法容易得到A=1,B=-1,即即对于一个n位十进制数p1p2…pn-1pn,则p1
p2…pn-1
是n-1位十进制数。例1求n位十进制数中出现偶数个5的数的个数。因此若令an表示n位十进制数中出现偶数个5的数的个数,bn表示出现奇数个5的数的个数,则有若它含有偶数个5,则pn必须取5以外的九个数中的一个;若p1p2…pn-1含有奇数个5,则pn必须取成5。a1=8,b1=1.设{an}的母函数为A(x),{bn}的母函数为B(x),则或者利用x2:x3:+)类似的还有这样就得到了关于A(x)和B(x)的联立方程组:可以解得:因此有由于另解:n-1位十进制数共有9×10n-2个,要么含有奇数个5,要么含有偶数个5。故有:因此有因此有(1)不出现a1,这相当于从其他n-1个元素中取r个做可重组合;这样的组合可以分为两种情况:(2)出现a1,这相当于从n个元素中取r-1个做可重组合再加上a1。因此有初始条件为因此还可以令例2从n个不同的元素a1,a2,…,an中取r个做允许重复的组合,求不同的组合数注意到递推关系
中有2个参数,对于固定的n,
的母函数为Gn(x),则因此有因此由二项式展开定理可知2.Fibonacci数列Fibonacci数列是递推关系的又一个典型问题,数列的本身有着许多应用。有雌雄兔子一对,假定过两月便可繁殖雌雄各一的一对小兔。问过了n个月后共有多少对兔子?设满n个月时兔子对数为Fn,其中当月新生兔数目设为Nn
对,上个月留下的兔子数目设为On对,则但是注意到On=Fn-1,Nn=On-1=Fn-2,因此有利用这个递推关系很容易可以得到:下面我们利用母函数来计算Fn的通项表达式。设Fn的母函数为G(x),则x3:x4:+)方程1-x-x2=0的两个根设为:则有利用待定系数法易有因此有即通项表达式为:下面介绍一些关于Fibonacci数列的结论。(1)任意正整数N可以表示成Fibonacci数列中的数的有限和,即满足si=0或1,且sisi+1=0。(2)边长为Fn的正方形可以分解为若干个边长为Fi和Fi+1的长方形。参见课本图形。0.618方法:将三分法中的2/3换成0.618。不妨假设区间为[0,1],上一步的取值点为x,1-x。为了充分利用上一步取值点的信息,因此要
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- Unit 2 Colours and Clothes Lesson 7公开课教学课件【七年级英语上册(冀教版)】
- 【初中语+文】《虽有嘉肴》课件+统编版语文八年级下册
- 2024年生活时尚-出国知识笔试参考题库含答案
- 2024年甘肃住院医师-甘肃住院医师口腔正畸科笔试参考题库含答案
- 2024年火电电力职业技能鉴定考试-变电运行工笔试参考题库含答案
- 美丽中国风景作文800字高中
- 2024年河南住院医师-河南住院医师中医眼科笔试参考题库含答案
- 2024年水路交通运输技能考试-船舶钳工笔试参考题库含答案
- 市政机械项目商业计划书及实施方案|瑞克咨询|2024年编|
- 2024年机械制造行业技能考试-铆工笔试参考题库含答案
- 合作办学工作实施方案范本
- 生产线智能调度系统
- 仁爱版七年级英语说课稿课件
- 部编版八年级语文上册(课本全册)课后习题参考答案
- 珍爱生命远离毒品小学公开课一等奖市赛课获奖课件
- 2023年副主任医师(副高)-消化内科学(副高)考试历年真题摘选带答案
- 防洪应急预案演练脚本(通用3篇)
- 2019年广东省音乐高考招生统一考试乐理试卷
- 中考英语二轮复习语法专题考前突击训练专题06 中考常考短语词组固定搭配100题 (含详解)
- 2022北京东城汇文中学初一(下)期中英语试卷及答案
评论
0/150
提交评论