组合数学中几个典型递归关系的讨论-大学论文.doc

《组合数学中几个典型递归关系的讨论-大学论文.doc》由会员分享，可在线阅读，更多相关《组合数学中几个典型递归关系的讨论-大学论文.doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目 录1引言12组合数学13递归关系23.1 递归思想23.2 递归关系24 FIBONACCI数列34.1问题的提出34.2问题的分析34.3问题的解答44.4 递归算法44.5 一类广义Fibonacci数列递归关系55 HANOI塔问题85.1问题的提出85.2问题的分析85.3问题的解答85.4 递归算法95.5 基于递归关系下Hanoi塔问题的推广106平面分割问题116.1问题的提出116.2问题的分析116.3问题的解答127结束语12参考文献13致谢14组合数学中几个典型递归关系的讨论Xxxxxx系本xxxxx班 xxxxxx指导教师： xxxxxxx摘 要：本文对几个典型的递

2、归关系进行了分析研究，分别为Fibonacci数列、Hanoi塔问题、平面分割问题。通过对问题的提出、分析、解答，从而求解出递归关系，并且对前两个问题有推广及总结，以发散性思维对Fibonacci数列、Hanoi塔问题的一般化问题进行了研究推理，并得到其递归关系。关键词：递归，Fibonacci数列，Hanoi塔问题，平面分割问题。Discussion on Several Typical Recursion Relations in Combinatorial Mathematics JxxxxxxClass xxxxx, Mathematics DepartmentTutor: xxxxx

3、xxxxAbstract: This paper mainly studies several typical recursion relations respectively, they are the Fibonacci Sequence. Hanoi Tower and Planar Segmentation Problem. The paper aims to find out the recursion relations and have a generalization and summary on the first two problems for them by propo

4、sing, analyzing and handling problems, then study and inference the general problems of Fibonacci Sequence and Hanoi Tower with divergent thinking, and work out the recursion relations finally.Key words: recursion, Fibonacci sequence, Hanoi tower, planar segmentation problem.131引言递归关系是数学与计算机科学的一个重要研

5、究对象，特别是在算法分析中有着广泛的应用。Fibonacci数列是由意大利的数学家Fibonacci提出的，人们从不同的角度得到了它的关系式，同时它与黄金分割数也有着联系，因此Fibonacci数列又称为黄金分割数列。研究表明，该数列在计算数学、优化理论、运筹学、现代物理、化学等领域都有着广泛的应用。通过对这个数列进行扩展，得到广义Fibonacci数列，1关于此目前已有不少研究成果。我们则对一类特殊的广义Fibonacci数列进行总结论述。Hanoi塔问题是组合数学的著名问题之一，亦是递归算法的典型例子，是由法国数学家卢卡斯提出的，标准的Hanoi塔问题虽已得到了解决，但是对于一般化的问题研

6、究成果却尚未成熟，我们对此将有一些简单的提及。平面分割问题亦是组合数学中的一个较为典型的例子，以下我们将逐一进行分析求解。2组合数学组合数学问题在生活中随处可见，其历史渊源扎根于数学娱乐和数学游戏中，例如幻方、Nim取子游戏，四色问题等。2近几十年来组合数学急速发展，其一部分原因在于计算机所发挥的重要影响，由于计算机不能独立运行，需要编程来控制。而这些程序的基础往往是求解问题的组合学算法。对于这些算法，运行时间效率与储存需求分析需要更多的组合学思想；另一部分的原因是组合数学在那些过去很少与数学接触的学科的适用性，如社会科学、生物科学、信息论等领域。组合数学涉及到将一个集合的物体排列成满足一些指

7、定规则的格式，在这里排列的存在性与排列的计数和分类这两类问题反复出现。一般来说，组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。而在实践中的研究，对于这些问题却往往存在着不能兼顾的困难。组合数学的主要工具之一便是数学归纳法，它与递归的思想在某种程度上是相同的。事实上，递归的数学模型就是归纳法。归纳是一个强有力的过程，在组合数学中尤其如此，其部分技巧是找到假设的正确平衡进行归纳。3递归关系3.1递归思想程序调用自身的编程技巧称为递归，它作为一种算法在计算机程序设计语言中有广泛的应用。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归的能力在于用有限的

8、语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。在计算机算法的应用中，递归算法一般用于解决三类问题：第一，数据的定义是按递归定义的，如Fibonacci函数；第二，问题解法按递归算法实现；第三，数据的结构形式是按递归定义的。但递归算法运行效率较低；在调用过程中，系统为每一层的返回点、局部量等开辟了栈来存储，而递归次数过多容易造成栈溢出等问题。3.2递归关系仅凭观察要得到一个序列的第个数的一般表达式是非常困难的，它通常是由递归关系和边界条件一起来描述的，而我们所要做的在于通过求解递归关系，从而得到序列的第个

9、数的一般表达式。定义 对于数列，.，.把该数列中除了有限个数以外的任何数和它前面的一个或一些数关联起来的方程叫做递归关系。为了能着手计算，须知数列中一个或一些数，这样的数叫做边界条件。对于递归关系的求解，主要是利用母函数法，此外还有迭代法等，以下简单介绍母函数法的求解。3对形如 的递归关系。，.，为该问题给定的边界条件，均为常数。设为序列，.，.的母函数，于是我们有，用乘式两边，然后从到求和，即.因为，.故可解出，即 其中，.，的值可任意取而不影响时的值。由，.，我们可得出，然后将上式右端展开成幂级数，则可知，即是得到序列，.，.的第个数的一般表达式。4 Fibonacci数列4.1问题的提出

10、Fibonacci数列的提出者是意大利比萨的数学家Leonardo Fibonacci(列昂纳多斐波那契)，他在1202年出版的书Liber Abaci（珠算原理）里面以兔子繁殖为例子引入，故该数列又称为“兔子数列”。Leonardo Fibonacci提出的问题如下：假定雌雄各一的每一对兔子每过两个月便可繁殖雌雄各一的一对小兔子，现有雌雄各一的兔子一对，假设所有的兔子都不死，问过了个月后共有多少对兔子？4.2问题的分析我们对以上问题进行简要的分析：设是过了个月后的兔子对数，令；在过了两个月，这对兔子要产一对新兔子，因而；在过了三个月时只有原来那对兔子产一对新兔子，故；在过了四个月时原来的一对

11、兔子和在过了两个月时产的一对兔子都要产一对新兔子，故；以此类推，便知在过了个月时兔子对数=过了个月时兔子对数+过了个月时兔子对数，故；，,.于是，通过分析我们得到了如下的递归关系：；，,.。其中，为边界条件。4.3问题的解答我们用母函数法对上述递归关系进行求解：设为序列，.，.的母函数，于是我们有以下式子：，而又由边界条件，则可得到，有+.即有，于是，联立方程与，得，.故，将上式右端展开成幂级数，其中的系数为.利用以上式子，或者是之前我们所得到的递归关系，我们可以得出：；.于是，我们给出如下定义：定义 令，,.依次写出数列，就是，.，那后一项等于前两项之和，这就是斐波那契数列，其中的任一个数，

12、都叫斐波那契数。4.4递归算法以下是用C语言编程，求Fibonacci数列前40个数。4#include void main() long int , ; int i; ,;for(i=1;i=20;i+) printf(“%12ld,%12ld”, , ); if(i%2=0) printf(“n”); ; ；4.5一类广义Fibonacci数列递归关系Fibonacci数列的应用很广，在物理、化学、准晶体结构等领域，都有直接应用，美国数学会自1960年起出版了斐波那契数列季刊，专门为刊载这方面的研究成果。对于Fibonacci数列的应用，我们在这里不一一赘述了。而将Fibonacci数列进

13、行推广，有斐波那契-卢卡斯数列；广义斐波那契数列。5以下我们看一类特殊的广义Fibonacci数列。6Fibonacci Log数列，简称为Log数列，该数列有如下叙述：假设初始时有一对小兔子，需要代的时间可以长成大兔子，之后每隔代又可生下对小兔子，问在第代时共有多少对兔子？以下对Log数列问题进行求解。设Log数列中第代兔子的数目共有对，对第代兔子的来源进行分析，我们可以得到第代兔子由以下的两部分组成：第代老兔子，其数目为；第代新生的新兔子，这群新兔子乃是由两部分的老兔子所生，一部分是第代刚长成大兔子的兔子，该部分兔子在代出生，其数目为；另一部分是第代生过新兔子的老兔子，这部分兔子在第代还可

14、以继续生下新兔子，其数目为.由此，可以推导出Log数列的递归关系，即为：，边界条件为，.显然，Fibonacci数列可以看成是Log数列中当，时的特殊情况，将这种特殊情况带入，则有，显然，经过整理，该递归关系的表达式与Fibonacci数列的递归关系表达式是一致的。我们将Fibonacci Log数列继续进行扩展，并命名为Fibonacci LogP数列，简称为LogP数列，假设每对兔子只可以生育代兔子，则问在第代时共有多少对兔子？以下对LogP数列问题进行求解。我们引入另一个参数，表示每对兔子只可以繁殖代（在Log数列中，即假设兔子如果可以无限繁殖的，即可看做是）。那么，在第代的兔子中，乃是

15、由以下两部分组成：第代的老兔子，其数目为；第代新生的新兔子，这群新兔子乃是由两部分的老兔子所生，并且还要除去不能继续繁殖的老兔子的数目，其数目分别记在下面：第代刚长成大兔子的兔子，该部分兔子在代时出生，其数目为；第代生过新兔子的老兔子，这部分兔子在第代还可继续生下新兔子，其数目为；第代不能继续繁殖的老兔子已经繁殖了代，这一类兔子在代时出生，其数目为.于是，LogP数列的递归关系为：.我们已经得出了以上所说广义Fibonacci数列的递归关系式，该类数列具有一定的物理含义，很有实用价值。其应用如在网络场景中，要求每台主机在收到父节点发来的多播消息后进行多播，在初始接收到消息后，主机需要时间进行数

16、据准备，随后每隔时间同时对台机器进行多播，求在时间时，有多少台机器接收到消息，这类问题就是Log数列。但是在实际网络场景中，每台主机所连接的机器数目不可能是无限多，假设每台主机连接了台机器，这样只需轮多播，该主机就完成了广播，这种情况下求解在时间时，有多少台机器接收到了消息，该类问题对应就是LogP数列。我们对此进一步进行推广，引入参数，令表示不生育后的老兔子还可以存活代，之后便死亡。接下来我们对第代的兔子的构成进行讨论，可由两部分组成：第代的老兔子，这部分老兔子数乃是由第代的老兔子数减去第代将要死去的老兔子数，分别如下：第代的老兔子，其数目为；第代将要死去的老兔子，这部分兔子是在代时出生的，

17、其数目为.第代新生的新兔子，这群新兔子乃是由两部分的老兔子所生，并且还要除去不能继续繁殖的老兔子的数目，其数目分别记在下面：第代刚长成大兔子的兔子，该部分兔子在代时出生，其数目为；第代生过新兔子的老兔子，这部分兔子在第代还可继续生下新兔子，其数目为；第代不能继续繁殖的老兔子已经繁殖了代，这一类兔子在代时出生，其数目为.于是，此数列的递归关系为：.如LogP数列在网络场景中的应用，我们知道，其主机接收到消息自然是不能无期限的储存的，因为内存的限制，所以我们假设消息储存时间后便将自动删除，这便是我们以上数列的对应。5 Hanoi塔问题5.1问题的提出汉诺塔又称为河内塔，是由法国数学家爱德华卢卡斯提

18、出的，他曾编写过一个印度的古老传说：在世界中心贝拿勒斯（位于印度北部）的圣庙里，有一块黄铜板，上面插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从上到下的穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在移动这些金片，他一次只能移动一片，而且不管在哪根针上，小片必须在大片的上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上面移动到另外一根针上面时，世界就将会在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。这当然只是一个传说，但是由此却引出了我们接下来所将要讨论的Hanoi塔问题：Hanoi塔由个大小不同的圆盘和三根木柱，组成，开始时，这个盘子由

19、大到小依次套在柱上，现在要求把柱上的个圆盘移到柱上，一次只能移一个圆盘，且圆盘只能在三根柱子上放，而在移动圆盘的过程中，不允许大圆盘压小圆盘，问总计需要移动多少个盘次？5.2问题的分析我们对上述的问题进行分析：令将圆盘从柱上移到柱上所需移动盘次，容易知道，当时，有，即我们只需移动一个盘次；当时，有，即我们需要先将小圆盘移到柱上，然后再将大圆盘移到柱上，之后再将小圆盘从柱上移到柱上，共需要移动三次；依此类推，当有个圆盘时，我们需要先设法先将上面的个圆盘均移到柱上，然后再将第个圆盘移到柱上，之后再将柱上的个圆盘移到柱上，由此，我们便求得了以下的式子：，；，.于是，通过分析，我们得到了如下的递归关系

20、：；，.其中，为边界条件。5.3问题的解答我们用母函数法对上述的递归关系式进行求解：设为序列，.，.的母函数，因，故，有，于是，我们得，令，得，解之，得，.我们有，将之右端展开成幂级数，于是便得到，其中的系数为.当时，我们有.让我们回到原始的汉诺塔问题，假如每秒钟可移动一次金片，那么，以上这个数字表明如果我们要想移完64片金片，一共需要5845.54亿年以上，而地球存在至今也不过几十亿年而已。5.4递归算法以下是用C语言编程，求解Hanoi塔问题。4#include void main() void hanoi(int n,char one,char two,char three);int m

21、;printf(“input the number of diskes:”);scanf(“%d”,&m);printf(“The step to moveing %d diskes:n”,m);hanoi(m,A,B,C); void hanoi(int n,char one,char two,char three) void move(char x,char y);if(n=1)move(one,three);else hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); void move(char x,

22、char y) printf(“%c%cn”,x,y);以上我们所给出的程序是Hanoi塔问题的递归算法解，事实上现在Hanoi塔问题也有非递归算法解，7但其算法实际上也是由递归算法演变而来的，我们这里便不详加讨论了。5.5基于递归关系下Hanoi塔问题的推广Hanoi塔问题是一个古典的数学问题，在数学界有着很高的研究价值，而且至今仍在被一些数学家们所研究；同时它也是一种趣味智力游戏，可以帮助人们开发智力，并且激发人的思维，所以，这个游戏被世界上不少国家的成人和儿童所喜爱。早在1883年爱德华卢卡斯不仅提出并且解决了Hanoi塔问题，而针对一般化的Hanoi塔问题目前研究成果却不多。在标准的H

23、anoi塔问题的前提下，我们改变其初始条件，来讨论一般化的Hanoi塔问题。8假设在柱上有种不同大小的圆盘，其从上到下对应的数目为，.，个，现在将所有的圆盘从柱上移到柱上，若同种类型圆盘的顺序可以任意，其他条件则与标准Hanoi塔问题相同，问总计需要移动多少个盘次？假设利用个柱子算法，将个圆盘从柱上移到柱上共需要移动个盘次。当时，将个大小相同的圆盘移到柱上，即有；当时，先将个圆盘从柱上移到柱上，再将个圆盘从柱上移到柱上，最后将个圆盘从柱上移到柱上，即有.依此类推，当柱上有种不同大小的圆盘时，先将上方类圆盘从柱上移到柱上，再将第类圆盘从柱上移到柱上，最后将之前类圆盘移到柱上。由此，我们得到以下递

24、归关系：.应用母函数法将之求解，可得.通过改进，我们对于一般化了的Hanoi塔问题进行了探讨，这样的结论在组合数学、人工智能、算法分析等领域都均有一定的参考价值。6平面分割问题6.1问题的提出平面分割问题是一个几何计数问题。它的表述如下：有条封闭曲线，其中任意两条恰好相交于两点，且任意三条不相交于同一点，问这条封闭曲线把平面分割成的区域个数？6.2问题的分析我们对上面的问题进行分析：设条封闭曲线把平面分割成为个区域。易知，当时，我们有，整个平面为一个区域；当时，有，封闭曲线里面的区域和封闭曲线外面的区域；当时，我们有；当时，有；当时，有.由此 ，我们得到如下递归关系：设，而条封闭曲线把平面分割

25、成的区域个数为，于是第条封闭曲线与这条封闭曲线相交于个点，这些点将第条封闭曲线截成段弧线，而这些弧与原来的条封闭曲线所形成的区域也即个区域相交，故新增了个区域，由此，我们可以得到这样的式子：，.于是，通过分析，我们得到了如下的递归关系：；，.其中，为边界条件。6.3问题的解答下面我们用母函数法对上述的递归关系式进行求解：设为序列，.，.的母函数，于是我们有以下式子：.+.，由于边界条件，故我们可以得到，有，有，故有，将上式右端展开成幂级数，有 .其中，项的系数即是递归关系的解，有，即，.平面分割问题的表述与推广还有很多，例如：直线分割平面问题与平面分割空间问题等，我们这里只简要的提及，便不一一

26、分析求解了。97结束语递归关系在组合数学中的应用，自然不仅限于以上所说的这几个例子。而对于以上几个例子的分析求解，也仅是对前人的研究进行了总结与论述，使我们对递归的思想及其在组合数学中的应用有更深刻的认识与更清楚了解，也使我们对目前的研究成果有所了解，以便我们可以在此基础上继续的探索、研究、创新，使其得到更好的发展，也更好的实现其应用价值。参考文献1 陈淑贞,曾庆年.广义Fibonacci数列的通项及性质J.海军工程大学学报, 2008,20(3).2 （美）布鲁迪（brualdi,R.A.）.组合数学M.北京:机械工业出版社,2001:1-13.3 杨振生.组合数学及其算法M.合肥:中国科学

27、技术大学出版社,1997:102- 127.4 谭浩强.C程序设计M.北京:清华大学出版社,2005:125-126,174-177.5 谭毓澄.Fibonacci数列新的递归形式及其推演J.科技通报.2012,28(1).6 徐伟.一类广义 Fibonacci数列递归关系的推导J.合肥学院学报（自然科学版）,2013,23(1).7 张世禄.Hanoi塔问题的最佳解法J.四川师范学院学报（自然科学版）, 2001, 22(4).8 周武,陈声利,谢辉.基于递归关系下的Hanoi塔问题研究J.西南民族大学学报（自然科学版）,2009,35(5).9 管训贵.直线分割平面问题的推广J.济南职业学院学报,2011,(3).致谢本论文是在指导老师老师的亲切关怀悉心指导下完成的，论文从开题、写作到定稿，我深深得益于老师的谆谆教诲。能师从老师，我实在感到无比庆幸，在此谨想老师表示我最深切的感激。在此期间得到同学们热心的帮助，同样向她们表示谢意。同时也要向大学期间辛勤培养教导我的各位老师献上真挚的敬意！