算法合集之《递推关系的建立及在信息学竞赛中的应用》

递推关系的建立及在信息学竞赛中的应用安徽高寒蕊-１-递推关系的建立及在信息学竞赛中的应用安徽高寒蕊(芜湖一中，安徽，241000)【关键字】递推关系建立应用【摘要】世界上的一切事物都在不经意之中变化着，在这纷繁的变幻中，许多现象的变化是有规律可循的。这种规律往往呈现出前因和后果的关系，故我们可以运用递推的思想去研究这些变化。本文着重说明了递推关系的建立，并在此基础上简略介绍求解递推关系的方法。接着，阐明递推关系与动态规划之间的关系，并比较了一般递推关系与动态规划之间的异同，同时举例说明递推关系在竞赛中的应用。在文章的最后，总结出学好递推关系，不仅可以提高我们的数学素质，对信息学竞赛更是大有帮助目录【正文】第02页一、引论第02页二、递推关系的定义第02页三、递推关系的建立第02页⒈五种典型的递推关系第03页⒉递推关系的求解方法第06页四、递推关系的应用第06页五、总结第10页递推关系的建立及在信息学竞赛中的应用安徽高寒蕊-２-【附录】第10页【参考书目】第12页【程序描述】第12页【正文】一、引论瞬息变幻的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。即是说，某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。所谓“三岁看老”，说的就是这个道理。这一道理也正体现了递推的思想。递推关系几乎在所有的数学分支中都有重要作用，在一切向“更快、更高、更强”看齐的当今信息学奥林匹克竞赛中更因简洁高效而显示出其独具的魅力。在递推关系发挥重要作用的今天，深入研究其性质、特点便成为一件十分必要的事情。本文就将围绕着递推关系的三大基本问题中的如何建立递推关系展开论述，并通过例题说明递推关系在当今信息学竞赛中的应用。二、递推关系的定义相信每个人对递推关系都不陌生，但若要说究竟满足什么样的条件就是递推关系，可能每个人又会有不同的说法。为了更好地研究递推关系，首先让我们明确什么是递推关系。【定义1】给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hn(0in)联系起来，这样的式子就叫做递推关系。三、递推关系的建立递推关系中存在着三大基本问题：如何建立递推关系，已给的递推关系有何性质，以及如何求解递推关系。如果能弄清楚这三个方面的问题，相信我们对递推关系的认识又会推进一步。由于篇幅所限，本文着重论述三大基本问题之一的如何建立递推关系。建立递推关系的关键在于寻找第n项与前面几项的关系式，以及初始项的值。它不是一种抽象的概念，是需要针对某一具体题目或一类题目而言的。在下文中，我们将对五种典型的递推关系的建立作比较深入具体的讨论。递推关系的建立及在信息学竞赛中的应用安徽高寒蕊-３-1．五种典型的递推关系Ⅰ.Fibonacci数列在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中，就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中，Fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题的提出：有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？解：设满x个月共有兔子Fx对，其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数目设为Ox对。则：Fx=Nx+Ox而Ox=Fx-1，Nx=Ox-1=Fx-2(即第x-2个月的所有兔子到第x个月都有繁殖能力了)∴Fx=Fx-1+Fx-2边界条件：F0=0，F1=1由上面的递推关系可依次得到F2=F1+F0=1，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，……。Fabonacci数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”[1]问题、下文中的『例题1』等都可以用这种方法来解决。在优选法[2]中，Fibonacci数列的用处也得到了较好的体现。Ⅱ.Hanoi塔问题问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。abc图1递推关系的建立及在信息学竞赛中的应用安徽高寒蕊-４-问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？解：设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。∴hn=2hn-1+1边界条件：hn-1=1Ⅲ.平面分割问题问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。解：设an为n条封闭曲线把平面分割成的区域个数。由图2可以看出：a2-a1=2；a3-a2=4；a4-a3=6。从这些式子中可以看出an-an-1=2(n-1)。当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后，第n-1条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，且第n条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an-1+2(n-1)，边界条件是a1=1。平面分割问题是竞赛中经常触及到的一类问题，由于其灵活多变，常常让选手感到棘手，下文中的『例题2』是另一种平面分割问题，有兴趣的读者不妨自己先试着求一下其中的递推关系。Ⅳ.Catalan数Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，把12132412346578图21234567108911121314n=1n=2n=3n=4递推关系的建立及在信息学竞赛中的应用安徽高寒蕊-５-n边形拆分成若干三角形，不同的拆分数目用hn表之，hn即为Catalan数。例如五边形有如下五种拆分方案(图6-4)，故h5=5。求对于一个任意的凸n边形相应的hn。解：设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边，边P1Pn也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，只要在P2，P3，……，Pn-1点中找一个点Pk(1kn)，与P1、Pn共同构成一个三角形的三个顶点，就将n边形分成了三个不相交的部分(如图3所示)，我们分别称之为区域①、区域②、区域③，其中区域③必定是一个三角形，区域①是一个凸k边形，区域②是一个凸n-k+1边形，区域①的拆分方案总数是Ck，区域②的拆分方案数为Cn-k+1，故包含△P1PkPn的n边形的拆分方案数为CkCn-k+1种，而Pk可以是P2，P3，……，Pn-1种任一点，根据加法原理，凸n边形的三角拆分方案总数为112inniiCC，同时考虑到计算的方便，约定边界条件C2=1。Catalan数是比较复杂的递推关系，尤其在竞赛的时候，选手很难在较短的时间里建立起正确的递推关系。当然，Catalan数类的问题也可以用搜索的方法来完成，但是，搜索的方法与利用递推关系的方法比较起来，不仅效率低，编程复杂度也陡然提高。Ⅴ.第二类Stirling数在五类典型的递推关系中，第二类Stirling是最不为大家所熟悉的。也正因为如此，我们有必要先解释一下什么是第二类Strling数。【定义2】n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。下面就让我们根据定义3来推导带两个参数的递推关系——第二类Stirling数。解：设有n个不同的球，分别用b1,b2,……bn表示。从中取出一个球bn，bn的放法有以下两种：①bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为S2(n-1,m-1)；②bn与别的球共占一个盒子；那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为mS2(n-1,m)。图3P1Pn①②③图4P2P3PkPn--1递推关系的建立及在信息学竞赛中的应用安徽高寒蕊-６-综合以上两种情况，可以得出第二类Stirling数定理：【定理】S2(n,m)=mS2(n-1,m)+S2(n-1,m-1)(n1,m1)边界条件可以由定义2推导出：S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。第二类Stirling数在竞赛中较少出现，但在竞赛中也有一些题目与其类似，甚至更为复杂。读者不妨自己来试着建立其中的递推关系。小结：通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。2．递推关系的求解方法求解递推关系最简单易行的方法是递推，递推是迭代算法中一种用若干步可重复的简单运算来描述复杂数学问题的方法，以便于计算机进行处理。它与递推关系的思想完全一致，由边界条件开始往后逐个推算，在一般情况下，效率较高，编程也非常的方便。但是，我们一般只需要求递推关系的第n项，而边界条件与第n项前面之间的若干项的信息是我们不需要的，如果采用递推的方法来求解的话，第n项之前的每一项都必须计算出来，最后才能得到所需要的第n项的值。这是递推无法避免的，从而在一定程度上影响了程序的效率。当然在大多数情况下，采用递推的方法还是可行的，在竞赛中，使用递推的方法编程，通常会在时限内出解。当然，更好的求解方法还有母函数法、迭代归纳法等等，这里就不再一一展开论述了。例如同样是对于Fibonacci数列问题：递推的方法要从F1，F2开始逐个推算出F3，F4……Fn，而利用母函数的方法，则可以得出公式5)251()251(nnnF，则可直接求出所需要的任意一项。四、递推关系的应用递推关系的应用十分的广泛，其中一个非常重要的应用就是著名的杨辉三角(又称“Pascal三角”，见图5)。杨辉三角是根据组合公式CCCrnrnrn111[3]画出来的。很显然，组合公式、杨辉三角都属于递推关系的范围。递推关系的建立及在信息学竞赛中的应用安徽高寒蕊-７-在今天的信息学竞赛中，递推关系的应用也日趋广泛，下面就让我们从近年来的两道竞赛题中体会递推关系的应用。『例1』(1998蚌埠市竞赛复试第一题)有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂房b的可能路线数。解：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行”的限制，决定了蜜蜂到b点的路径只能是从b-1点或b-2点到达的，故fn=fn-1+fn-2(a+2nb)，边界条件fa=1，fa+1=1。(附有程序Pr