信息学竞赛中问题求解常见题分析(二)

信息学竞赛中问题求解常见题分析（二）递推问题瞬息万变的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。即是说，某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。本文将围绕着递推关系的三大基本问题中如何建立递推关系展开论述，并通过例题说明递推关系在当今信息学竞赛中的应用。一、递推关系的定义相信每个人对递推关系都不陌生，但若要说究竟满足什么样的条件就是递推关系，可能每个人又会有不同的说法。为了更好地研究递推关系，首先让我们明确什么是递推关系。【定义l】给定一个数的序列H。，H1，……，Hn若存在整数no，使当n>=no时，可以用等号将Hn与其前面的某些项Hn。(0<=i<n)联系起来，这样的式子就叫做递推关系。二、递推关系的建立递推关系中存在着三大基本问题：如何建立递推关系，已给的递推关系有何性质，以及如何求解递推关系。建立递推关系的关键在于寻找第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)。故hs=5，求对于一个任意的凸n边形相应的hn。．解：设Cn表示凸n边形的拆分方案总数．由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边，边P1，Pn也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，只要在P2，P3……Pn-1点中找一个点Pk(1<k<n)，与P1，Pn共同构成一个三角形的三个顶点，就将n边形分成了三个不相交的部分(如图4所示)，我们分别称之为区域①．区域②，区域③，其中区域③必定是一个三角形，区域①是一个凸k边形，区域②是一个凸n-k+l边形，区域①的拆分方案总数是Ck，区域②的拆分方案数为Cn-k+1故包含△P1PKPN的n边形的拆分方案数为CkCn-k+1种，而Pk可以是P2，P3，……Pn-1种任一点，根据加法原理，凸n边形的拆分方案总数为。同时考虑到计算的方便，约定边界条件c2=1。小结：通过上面对四种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。三，倒题精讲例1．在一个正六边彤的六个区域中的每一个区域染上红、黄、蓝、紫四种颜色之一，要求相邻的两个区域染色不相同，则有多少种不同的染色方法?【分析】本问题属于排列组合方面的问题。【解答l】解法一：按染色情况进行分类：(1)若A，C，E染一种色，则此时共有4×3×3×3=108种方法：(2)若A，C，E染三种色，则此时共有P43×2×2×2=192种方法；(3)若A，C，E染两种色，剧此时共有P42×C32×3×2×2=432种．故总计有105+192+432=732种方法．解法二：将问题抽象成一般问题：“将圆分为n(n=>2)个扇形，每个扇形区域染上红、黄、蓝、紫四种颜色之一，要求相邻的扇形区域染色不相同，记染色方法总数为an，求a6”先不管第一个颜色与最后一个颜色是否相同，则有4x3n-1种方案。再减去第一个颜色与最后一个颜色相同的情况an-1：容易建立递推关系an=4×3n-1-an-1(n>=3)。a2=12由递推关系易求出a3=24，a4=84，a5=240，a6=32。【评注】(1)解法一中若不按A，C，E染色情况进行分类可能比较复杂，并且当A，C，E染两种色时，计算染法数比较容易出错；(2)解法二中关键之处在于建立递推式子，但递推式子建立后计算比较方便。例2．有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。试求出蜜蜂从蜂房a爬到蜂房b的可能路线。解：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行”的限制，决定了蜜蜂到b点的路径只能是从b-1点或b-2点到达的，故fn=fn-1+fn-2(a+2<=n<=b)，边界条件fa=1,fa+1=1。四、练习第1题(5分)：有5本不同的数学书分给5个男同学，有4本不同的英语书分给4个女同学．将全部书收回来后再重新发给他们，与原方案都不相同的方案有。答案：5！*4！+D(5)*D(4)=1140480其中：D(n)=(n-1)·(D(n-1)+D(n-2))(n>2)D(1)=0D(2)=1第2题(5分)：在m*n的棋盘上，每个方格(单位正方形，即边长为1的正方形)的顶点称为格点．以格点为顶点的多边形称为格点多边形．若设格点凸N边形面积的最小值为gn，格点凸N边形内部(非顶点的)格点的个数的最小值为fn，则gn和fn的关系式为答案：fn=fn+N／2-1(N>=3)第3题(8分)：有住小同学喜欢在方阵中填数字，规则是按图7例从右上角开始，按斜线填数字．碰到边界就重新开始。显然，数字1在坐标(1，5)位置，数字25在坐标(5，1)位置．后来这位小朋友想知道，对于H阶的方阵，随机取一个位置(x，y)，并规定x<Y，问这个位置上应填的数字是多少?5阶方阵的示例图如图7：11742116128532017139623211814102524221915答案：(N-y+x)*(N-y+x-1)／2+x第4题(5分)：把三角形各边分成n等份，过每