信息学竞赛中问题求解常见题分析（二）..docVIP

信息学竞赛中问题求解常见题分析（二） 递推问题 瞬息万变的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。即是说，某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。 本文将围绕着递推关系的三大基本问题中如何建立递推关系展开论述，并通过例题说明递推关系在当今信息学竞赛中的应用。 一、递推关系的定义 相信每个人对递推关系都不陌生，但若要说究竟满足什么样的条件就是递推关系，可能每个人又会有不同的说法。为了更好地研究递推关系，首先让我们明确什么是递推关系。 【定义l】给定一个数的序列H。，H1，……，Hn若存在整数no，使当n=no时，可以用等号将Hn与其前面的某些项Hn。(0=in)联系起来，这样的式子就叫做递推关系。 二、递推关系的建立 递推关系中存在着三大基本问题：如何建立递推关系，已给的递推关系有何性质，以及如何求解递推关系。建立递推关系的关键在于寻找第n项与前面几项的关系式，以及初始项的值。它不是一种抽象的概念，是需要针对某一具体题目或一类题目而言的。在下文中，我们将对五种典型的递推关系的建立作比较深入具体的讨论。 四种典型的递推关系 Ⅰ．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=l，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，…。 II．Hanoi塔问题 问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a，b，c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。 要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许大盘压小盘。 问将这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条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了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边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn．表示，hn即为Catafan数．例如五边彤有如下五种拆分方案(图3)。故h s=5，求对于一个任意的凸n边形相应的hn。． 解：