文档介绍：递推关系的建立及在信息学竞赛中的应用
【关键字】递推关系建立应用
【摘要】
世界上的一切事物都在不经意之中变化着,在这纷繁的变幻中,许多现象的变化是有规律可循的。这种规律往往呈现出前因和后果的关系,故我们可以运用递推的思想去研究这些变化。本文着重说明了递推关系的建立,并在此基础上简略介绍求解递推关系的方法。接着,阐明递推关系与动态规划之间的关系,并比较了一般递推关系与动态规划之间的异同,同时举例说明递推关系在竞赛中的应用。在文章的最后,总结出学好递推关系,不仅可以提高我们的数学素质,对信息学竞赛更是大有帮助。
目录
【正文】第02页
一、引论第02页
二、递推关系的定义第02页
三、递推关系的建立第02页
⒈五种典型的递推关系第03页
⒉递推关系的求解方法第06页
四、递推关系的应用第06页
五、总结第10页
【附录】第10页
【参考书目】第12页
【程序描述】第12页
【正文】
引论
瞬息变幻的世界,每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中,许多现象的变化是有规律的,这种规律往往呈现出前因和后果的关系。即是说,某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。所谓“三岁看老”,说的就是这个道理。这一道理也正体现了递推的思想。递推关系几乎在所有的数学分支中都有重要作用,在一切向“更快、更高、更强”看齐的当今信息学奥林匹克竞赛中更因简洁高效而显示出其独具的魅力。在递推关系发挥重要作用的今天,深入研究其性质、特点便成为一件十分必要的事情。本文就将围绕着递推关系的三大基本问题中的如何建立递推关系展开论述,并通过例题说明递推关系在当今信息学竞赛中的应用。
递推关系的定义
相信每个人对递推关系都不陌生,但若要说究竟满足什么样的条件就是递推关系,可能每个人又会有不同的说法。为了更好地研究递推关系,首先让我们明确什么是递推关系。
【定义1】给定一个数的序列H0,H1,…,Hn,…若存在整数n0,使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hn(0i<n)联系起来,这样的式子就叫做递推关系。
递推关系的建立
递推关系中存在着三大基本问题:如何建立递推关系,已给的递推关系有何性质,以及如何求解递推关系。如果能弄清楚这三个方面的问题,相信我们对递推关系的认识又会推进一步。由于篇幅所限,本文着重论述三大基本问题之一的如何建立递推关系。
建立递推关系的关键在于寻找第n项与前面几项的关系式,以及初始项的值。它不是一种抽象的概念,是需要针对某一具体题目或一类题目而言的。在下文中,我们将对五种典型的递推关系的建立作比较深入具体的讨论。

Ⅰ.i数列
在所有的递推关系中,i数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中,就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中,i数列类的题目因为解法相对容易一些,逐渐退出了竞赛的舞台。i数列没有研究价值,恰恰相反,一些此类的题目还是能给我们一定的启发的。
i于1202年提出的“兔子繁殖问题”(又称“i问题”)。
问题的提出:有雌雄一对兔子,假定过两个月便可繁殖雌雄各一的一对小兔子。问过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,……。
i数列常出现在比较简单的组合计数问题中,例如以前的竞赛中出现的“骨牌覆盖”[1]问题、下文中的『例题1』等都可以用这种方法来解决。在优选法[2]中,i数列的用处也得到了较好的体现。
Ⅱ.Hanoi塔问题
问题的提出:Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时,这n个圆盘由大到小依次套在a柱上,如图1所示。
a b c

图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柱上的小盘