文档格式 组合数学中几个典型递归关系的讨论 ㊣ 精品文档

🔯 格式:DOC | ❒ 页数:16 页 | ⭐收藏:0人 | ✔ 可以修改 | @ 版权投诉 | ❤️ 我的浏览 | 上传时间:2026-10-24 03:00
组合数学中几个典型递归关系的讨论第1页
第 1 页 / 共 16 页
组合数学中几个典型递归关系的讨论第2页
第 2 页 / 共 16 页
组合数学中几个典型递归关系的讨论第3页
第 3 页 / 共 16 页
组合数学中几个典型递归关系的讨论第4页
第 4 页 / 共 16 页
组合数学中几个典型递归关系的讨论第5页
第 5 页 / 共 16 页
组合数学中几个典型递归关系的讨论第6页
第 6 页 / 共 16 页
组合数学中几个典型递归关系的讨论第7页
第 7 页 / 共 16 页
组合数学中几个典型递归关系的讨论第8页
第 8 页 / 共 16 页
组合数学中几个典型递归关系的讨论第9页
第 9 页 / 共 16 页
组合数学中几个典型递归关系的讨论第10页
第 10 页 / 共 16 页
组合数学中几个典型递归关系的讨论第11页
第 11 页 / 共 16 页
组合数学中几个典型递归关系的讨论第12页
第 12 页 / 共 16 页
组合数学中几个典型递归关系的讨论第13页
第 13 页 / 共 16 页
组合数学中几个典型递归关系的讨论第14页
第 14 页 / 共 16 页
组合数学中几个典型递归关系的讨论第15页
第 15 页 / 共 16 页

,即我们需要先将小圆盘移到柱上,然后再将大圆盘移到柱上,之后再将小圆盘从柱上移到柱上,共需要移动三次依此类推,当有个圆盘时,我们需要先设法先将上面的个圆盘均移到柱上,然后再将第个圆盘移到柱上,之后再将柱上的个圆盘移到柱上,由此,我们便求得了以下的式子,于是,通过分析,我们得到了如下的递归关系其中,为边界条件。


问题的解答我们用母函数法对上述的递归关系式进行求解设为序列的母函数,,因,,故,有,于是,我们得,令,得,,解之,得,我们有,将之右端展开成幂级数,于是便得到,其中的系数为当时,我们有让我们回到原始的汉诺塔问题,假如每秒钟可移动次金片,那么,以上这个数字表明如果我们要想移完片金片,共需要亿年以上,而地球存在至今也不过几十亿年而已。


递归算法以下是用语言编程,求解塔问题。


,以上我们所给出的程序是塔问题的递归算法解,事实上现在塔问题也有非递归算法解,但其算法实际上也是由递归算法演变而来的,我们这里便不详加讨论了。


基于递归关系下塔问题的推广塔问题是个古典的数学问题,在数学界有着很高的研究价值,而且至今仍在被些数学家们所研究同时它也是种趣味智力游戏,可以帮助人们开发智力,并且激发人的思维,所以,这个游戏被世界上不少国家的成人和儿童所喜爱。


早在年爱德华卢卡斯不仅提出并且解决了塔问题,而针对般化的塔问题目前研究成果却不多。


在标准的塔问题的前提下解,也使我们对目前的研究成果有所了解,以便我们可以在此基础上继续的探索研究创新,使其得到更好的发展,也更好的实现其应用价值。


参考文献陈淑贞,曾庆年广义数列的通项及性质海军工程大学学报美布鲁迪,组合数学北京机械工业出版社,杨振生组合数学及其算法合肥中国科学技术大学出版社,谭浩强程序设计北京清华大学出版社谭毓澄数列新的递归形式及其推演科技通报,徐伟类广义数列递归关系的推导合肥学院学报自然科学版张世禄塔问题的最佳解法四川师范学院学报自然科学版周武,陈声利,谢辉基于递归关系下的塔问题研究西南民族大学学报自然科学版管训贵直线分割平面问题的推广济南职业学院学报致谢本论文是在指导老师老师的亲切关怀悉心指导下完成的,论文从开题写作到定稿,我深深得益于老师的谆谆教诲。


能师从老师,我实在感到无比庆幸,在此谨想老师表示我最深切的感激。


在此期间得到同学们热心的帮助,同样向她们表示谢意。


同时也要向大学期间辛勤培养教导我的各位老师献上真挚的敬意我们改变其初始条件,来讨论般化的塔问题。


假设在柱上有种不同大小的圆盘,其从上到下对应的数目为,个,现在将所有的圆盘从柱上移到柱上,若同种类型圆盘的顺序可以任意,其他条件则与标准塔问题相同,问总计需要移动多少个盘次假设利用个柱子算法,将个圆盘从柱上移到柱上共需要移动个盘次。


当时,将个大小相同的圆盘移到柱上,即有当时,先将个圆盘从柱上移到柱上,再将个圆盘从柱上移到柱上,最后将个圆盘从柱上移到柱上,即有依此类推,当柱上有种不同大小的圆盘时,先将上方类圆盘从柱上移到柱上,再将第类圆盘从柱上移到柱上,最后将之前类圆盘移到柱上。


由此,我们得到以下递归关系应用母函数法将之求解,可得通过改进,我们对于般化了的塔问题进行了探讨,这样的结论在组合数学人工智能算法分析等领域都均有定的参考价值。


平面分割问题问题的提出平面分割问题是个几何计数问题。


它的表述如下有条封闭曲线,其中任意两条恰好相交于两点,且任意三条不相交于同点,问这条封闭曲线把平面分割成的区域个数问题的分析我们对上面的问题进行分析设条封闭曲线把平面分割成为个区域。


易知,当时,我们有,整个平面为个区域当时,有,封闭曲线里面的区域和封闭曲线外面的区域当时,我们有当时,有当时,有由此,我们得到如下递归关系设,而条封闭曲线把平面分割成的区域个数为,于是第条封闭曲线与这条封闭曲线相交于个点,这些点将第条封闭曲线截成段弧线,而这些弧与原来的条封闭曲线所形成的区域也即个区域相交,故新增了个区域,由此,我们可以得到这样的式子,,,于是,通过分析,我们得到了如下的递归关系其中,,为边界条件。


问题的解答下面我们用母函数法对上述的递归关系式进行求解设为序列的母函数,于是我们有以下式子,由于边界条件,故我们可以得到,有,有,故有,将上式右端展开成幂级数,有,其中,项的系数即是递归关系的解,有,,即,平面分割问题的表述与推广还有很多,例如直线分割平面问题与平面分割空间问题等,我们这里只简要的提及,便不分析求解了。


结束语递归关系在组合数学中的应用,自然不仅限于以上所说的这几个例子。


而对于以上几个例子的分析求解,也仅是对前人的研究进行了总结与论述,使我们对递归的思想及其在组合数学中的应用有更深刻的认识与更清楚而递归次数过多容易造成栈溢出等问题。


递归关系仅凭观察要得到个序列的第个数的般表达式是非常困难的,它通常是由递归关系和边界条件起来描述的,而我们所要做的在于通过求解递归关系,从而得到序列的第个数的般表达式。


定义对于数列,把该数列中除了有限个数以外的任何数和它前面的个或些数关联起来的方程叫做递归关系。


为了能着手计算,须知数列中个或些数,这样的数叫做边界条件。


对于递归关系的求解,主要是利用母函数法,此外还有迭代法等,以下简单介绍母函数法的求解。


对形如的递归关系。


,,,为该问题给定的边界条件,均为常数。


设为序列,的母函数,于是我们有,用乘式两边,然后从到求和,即因为,,故可解出,即其中,,的值可任意取而不影响时的值。


由,,,我们可得出,然后将上式右端展开成幂级数,则可知,即是得到序列,的第个数的般表达式。


数列问题的提出数列的提出者是意大利比萨的数学家列昂纳多斐波那契,他在年出版的书珠算原理里面以兔子繁殖为例子引入,故该数列又称为兔子数列。


提出的问题如下假定雌雄各的每对兔子每过两个月便可繁殖雌雄各的对小兔子,现有雌雄各的兔子对,假设所有的兔子都不死,问过了个月后共有多少对兔子问题的分析我们对以上问题进行简要的分析设是过了个月后的兔子对数,令在过了两个月,这对兔子要产对新兔子,因而在过了三个月时只有原来那对兔子产对新兔子,故在过了四个月时原来的对兔子和在过了两个月时产的对兔子都要产对新兔子,故以此类推,便知在过了个月时兔子对数过了个月时兔子对数过了个月时兔子对数,故,,于是,通过分析我们得到了如下的递归关系。


其中,,为边界条件。


问题的解答我们用母函数法对上述递归关系进行求解设为序列的母函数,于是我们有以下式子,而又由边界条件则可得到,有代刚长成大兔子的兔子,该部分兔子在代时出生,其数目为第代生过新兔子的老兔子,这部分兔子在第代还可继续生下新兔子,其数目为第代不能继续繁殖的老兔子已经繁殖了代,这类兔子在代时出生,其数目为于是,数列的递归关系为我们已经得出了以上所说广义数列的递归关系式,该类数列具有定的物理含义,很有实用价值。


其应用如在网络场景中,要求每台主机在收到父节点发来的多播消息后进行多播,在初始接收到消息后,主机需要时间进行数据准备,随后每隔时间同时对台机器进行多播,求在时间时,有多少台机器接收到消息,这类问题就是数列。


但是在实际网络场景中,每台主机所连接的机器数目不可能是无限多,假设每台主机连接了台机器,这样只需轮多播,该主机就完成了广播,这种情况下求解在时间时,有多少台机器接收到了消息,该类问题对应就是数列。


我们对此进步进行推广,引入参数,令表示不生育后的老兔子还可以存活代,之后便死亡。


接下来我们对第代的兔子的构成进行讨论,可由两部分组成第代的老兔子,这部分老兔子数乃是由第代的老兔子数减去第代将要死去的老兔子数,分别如下第代的老兔子,其数目为第代将要死去的老兔子,这部分兔子是在代时出生的,其数目为第代新生的新兔子,这群新兔子乃是由两部分的老兔子所生,并且还要除去不能继续繁殖的老兔子的数目,其数目分别记在下面第代刚长成大兔子的兔子,该部分兔子在代时出生,其数目为第代生过新兔子的老兔子,这部分兔子在第代还可继续生下新兔子,其数目为第代不能继续

下一篇
  • Hi,我是你的文档小助手!
    你可以按格式查找相似内容哟
筛选: 精品 DOC PPT RAR
小贴士:
  • 🔯 当前文档为word文档,建议你点击DOC查看当前文档的相似文档。
  • ⭐ 查询的内容是以当前文档的标题进行精准匹配找到的结果,如果你对结果不满意,可以在顶部的搜索输入框输入关健词进行。
帮帮文库-精品文档 帮帮文库-免费阅读 帮帮文库-海量资源
换一批