递推关系在信息学竞赛中的运用

《递推关系在信息学竞赛中的运用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、【止文】一、引论第02页第02页1•五种典型的递推关系第03页2•递推关系的求解方法第06页递推关系的建立及在信息学竞赛中的应用安徽高寒蕊（芜湖一中，安徽，241000）【关键字】递推关系建立应用【摘要】世界上的一切事物都在不经意之中变化着，在这纷繁的变幻中，许多现象的变化是有规律可循的。这种规律往往呈现出前因和后果的关系，故我们可以运用递推的思想去研究这些变化。本文着重说明了递推关系的建立，并在此基础上简略介绍求解递推关系的方法。接着，阐明递推关系与动态规划之间的关系，并比较了一般递推关系与动态规划之间的异同，同时举例说明递推关系在竞赛中的应用

2、。在文章的最后，总结岀学好递推关系，不仅可以提高我们的数学素质，对信息学竞赛更是大有帮助。目录第02页第02页二、递推关系的定义三、递推关系的建立第06页笫10页四、递推关系的应用五、总结【附录】【参考书目】【程序描述】第10页第12页第12页【正文】一、引论瞬息变幻的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。即是说，某种现彖的变化结果与紧靠它前而变化的一个或一些结呆紧密关联。所谓“三岁看老”，说的就是这个道理。这一道理也正体现了递推的思想。递推关系几乎在所

3、有的数学分支屮都有重要作用，在一切向“更快、更高、更强”看齐的当今信息学奥林匹克竞赛中更因简洁高效而显示出其独具的魅力。在递推关系发挥重要作用的今天，深入研究其性质、特点便成为一件十分必要的事情。本文就将围绕着递推关系的三大基本问题屮的如何建立递推关系展开论述，并通过例题说明递推关系在当今信息学竞赛中的应用。二、递推关系的定义相信每个人对递推关系都不陌生，但若要说究竟满足什么样的条件就是递推关系，可能每个人乂会有不同的说法。为了更好地研究递推关系，首先让我们明确什么是递推关系。【定义1】给定一个数的序列HO,H1,…,Hn,・・喏存在整数no,使

4、当n>no时,可以用等号(或大于号、小于号)将弘与其前面的某些项Hn(OGvn)联系起来，这样的式子就叫做递推关系。三、递推关系的建立递推关系中存在着三大基本问题：如何建立递推关系，已给的递推关系有何性质，以及如何求解递推关系。如果能弄清楚这三个方而的问题，相信我们对递推关系的认识乂会推进一步。由于篇幅所限，本文着重论述三大基本问题之一的如何建立递推关系。建立递推关系的关键在于寻找第n项与前面几项的关系式，以及初始项的值。它不是一种抽象的概念，是需耍针对某一具体题目或一类题目而言的。在下文屮，我们将对五种典型的递推关系的建立作比较深入具体的讨论。

5、I.五种典型的递推关系I.Fibonacci数列在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言屮，就有很多这类的题口。而在较为复杂的Basic>PascaLC语言中,Fibonacci数列类的题目因为解法相对容易一些,逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值，恰恰相反，一些此类的题目述是能给我们一定的启发的。Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称"Fibonacci问题”)。问题的提出：有雌雄

6、一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔了。问过n个月后共有多少对兔了？解：设满x个月共冇兔子玖对，其中当月新生的兔子数目为M对。第x・l个刀留下的兔子数目设为Q对。贝・Fx二Nx+Ox而0尸Fx_i，二玖_2(即第x-2个月的所有兔了到第x个月都有繁殖能力了)・・・Fx=Fx_1+Fx_2边界条件：Fo=O,F1=l由上面的递推关系可依次得到F2=F1+Fo=l,F3=F2+F]=2,F4=F3+F2=3,F5=F4+F3=5,oFabonacci数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”山问题、下文屮的『

7、例题1J等都可以用这种方法来解决。在优选法⑵中，Fibonacci数列的用处也得到了较好的体现。I.Hanoi塔问题问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上:(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘了从a柱移动到c柱上，总计需要移动多少个盘次？解：设入为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=l时，，只需把a柱上的盘子直接移动到c柱就可以了，故h1=

8、lo当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=