国家集训队2000论文集高寒蕊论文

《国家集训队2000论文集高寒蕊论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、2页第02页一、引论:、递推关系的定义三、递推关系的建立1・五种典型的递推关系第03页2•递推关系的求解方法第06页四、递推关系的应用第06页五、总结第10页【附录】【参考书目】【程序描述】第10页第12页第12页【正文】引论瞬息变幻的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻屮，许多现彖的变化是冇规律的，这种规律往往呈现岀前因和后果的关系。即是说，某种现彖的变化结果与紧靠它前面变化的一个或一些结果紧密关联。所谓“三岁看老”，说的就是这个道理。这一道理也正体现了递推的思想。递推关系几乎在所有的数学分支中都有重要作用，在一切向“更快、更高、更强”看齐

3、的当今信息学奥林匹克竞赛中更因简洁高效而显示出其独具的魅力。在递推关系发挥重要作用的今天，深入研究其性质、特点便成为一件十分必要的事情。本文就将围绕着递推关系的三大基本问题中的如何建立递推关系展开论述，并通过例题说明递推关系在当今信息学竞赛屮的应用。递推关系的定义相信每个人对递推关系都不陌生，但若要说究竞满足什么样的条件就是递推关系，可能每个人又会有不同的说法。为了更好地研究递推关系，首先让我们明确什么是递推关系。【定义1］给定一个数的序列Ho,Hi,・・•，£,•・喏存在整数no，使当n'lio时,可以用等号（或大于号、小于号）将弘与其前面的某些项弘（叱ivn）联系起来

4、，这样的式子就叫做递推关系。三.递推关系的建立递推关系屮存在着三大基本问题：如何建立递推关系，已给的递推关系有何性质，以及如何求解递推关系。如果能弄清楚这三个方面的问题，相信我们对递推关系的认识又会推进一步。由于篇幅所限，木文着重论述三大基木问题之一的如何建立递推关系。建立递推关系的关键在于寻找第n项与前面几项的关系式，以及初始项的值。它不是一种抽彖的概念，是需要针对某一具体题目或一类题目而言的。在下文中，我们将对五种典型的递推关系的建立作比较深入具体的讨论。1・五种典型的递推关系I.Fibonacci数列在所有的递推关系屮，Fibonacci数列应该是最为大家所熟悉的。

5、在最基础的程序设计语言Logo语言中，就冇很多这类的题0。而在较为复杂的Basic、Pascal.C语言中,Fibonacci数列类的题目因为解法相对容易一些,逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没冇研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题的提出：有雌雄一对兔了，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？解：设满x个刀共有兔子玖对，其中当刀新生的兔子数目为Nx对

6、。第x・l个月留下的兔子数口设为Ox对。贝山Fx=Nx+Ox而Ox=Fx-i‘Nx=0x_i=Fx_2(BOx-2个月的所冇兔子到第x个月都冇繁殖能力了)・・・Fx=Fx.1+Fx.2边界条件：Fo=O,F1=l由上面的递推关系可依次得到F2=F]+Fo=1,F3=F2+Fi=2,F4=F3+F2=3,F5=F4+F3=5,oFabonacci数列常出现在比较简单的组合计数问题屮，例如以前的竞赛屮出现的“骨牌覆盖”川问题、下文中的『例题1』等都可以用这种方法来解决。在优选法⑵屮，Fibonacci数列的用处也得到了较好的体现。II.Hanoi塔问题问题的捉出：Hanoi塔

7、由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图I所示。abc要求把a柱上n个圆盘按下述规则移到c柱上:(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？解：设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=l时*,只需把a柱上的盘子直接移动到c柱就可以了，故h尸1。当n=2吋，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上,