运用化归思想解决信息学中的数列问题

《运用化归思想解决信息学中的数列问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、运用化归思想解决信息学中的数列问题余余余林林林韵韵韵指指指导导导教教教师师师陈陈陈颖颖颖福福福建建建省省省福福福州州州第第第一一一中中中学学学高高高三三三9班班班2007年年年11月月月摘摘摘要要要数列是数学学科一个重要的分支，有着广泛的应用。从古至今有许多研究数列问题的经典论著。本文试图应用数学知识，从计算机解决问题的角度，结合信息学竞赛中的数列问题，展开分析、研究和讨论，提出解决数列问题的思维方法和技巧。向读者传达这样一个信息：解决数列问题不能墨守陈规，要敢于创新，联系所学知识，综合运用各种方法。本文共分为五章：第一章基础数学介绍解决数列问题涉及到的数学方法，为后面几

2、章数列问题的解决奠定基础。第二章运用数列的“周期性”化归本章选取了两道有代表性的例题，它们的背后隐藏着美妙的“周期性”。合理运用数列的“周期性”并结合一、二章提到的方法展开分析，大大降低了时间复杂度，有助于高效解决问题。这种方法对我们日后的解题也有所启发。第三章多元化方法化归解决数列问题本章选取了2007年NOIday2的第二题Count以及Ural上的1396号问题作为例题，在第三章合理运用数列“周期性”的基础上，介绍了通过化归、解决与数列相关的信息学问题的其他方法，主要有深入分析问题本质、寻找数列通项公式，分阶段考虑问题等。第四章总结本章简述了数列问题在信息学竞赛中的

3、重要地位，对之前四章的内容进行了分析、总结，并重复强调了本文中的重要思想方法。关键词：数列化归辗转相除法快速幂运算矩阵乘法周期性多元化方法目目目录录录摘要i目录ii前言1第一章预备知识31.1矩阵乘法...............................31.2辗转相除法..............................31.2.1辗转相除法..........................31.2.2辗转相除法的时间复杂度分析................51.2.3辗转相除法的扩展......................51.3快速计算常系数

4、线性递推数列的第N项..............61.3.1快速计算等比数列的第N项.................61.3.2快速计算广义Fibonacci数列的第N项...........61.3.3快速计算常系数线性递推数列的第N项..........7第二章合理运用数列的“周期性”92.1例一Dispute.............................92.2例二Abs数列.............................132.3小结..................................16第三章多元化方法化归解决数列问题18

5、3.1例三生成树计数...........................183.2例四Maximum............................24第四章总结28目录iii参考文献30感谢31前前前言言言随着计算机逐渐步入人们的生活，网络日趋普及，“信息革命”的到来。信息学作为一门新兴的学科,越来越引起世界各国的重视。跨入新世纪,随着素质教育的全面推进、课程改革的全面实施，我国的信息学教育课程已从小学开始成为学生的必修科目，并一直延伸到大学。信息学的学习需要掌握好数学物理等基础学科的知识，而通过信息学的学习和实践、运用，可培养严谨的逻辑思维能力，全面促进人的

6、创新精神的培养和全面素质的提高。在信息学的学习中，我们经常会遇到许多数列问题，在人类文明的发展进程中，人们对数列的研究可谓历史悠久。人类在古代随着自然数、分数的概念和四则运算的产生，为了生产和生活的需要，开始了对数列的研究。在世界数学史上，中国、巴比伦、古希腊、埃及和印度等，都曾经研究过级数，中国古代数学名著《周髀算经》《九章算术》《孔子算经》《张邱建算经》等，对等差级数a+(a+b)+(a+2b)+(a+3b)+:::+[a+(n¡1)b]和等比级数a+a¤q+a¤q2+a¤q3+:::+a¤qn¡1都列举出计算的例子，说明中国古代对级数的研究曾作出过一定的贡献。古老的

7、《易经》一书中写道：“是故《易》有太极，是生两仪；两仪生四象，四象生八卦”，实际上，这种分割，已经寓有数学中等比数列的思想。正由于数列知识在解决生产生活实际问题中具有重要作用，因此，世界各国从来就没有停止过对它的研究。我国更是把数列作为学习高等数学的基础和培养学生能力的良好题材，列入了高中数学的必修内容。参加过小学数学联赛的同学一定做过“找规律填数”这类趣题。而在信息学联赛中，也不乏很多有趣的数列题以及与数列相关的题目。本文将从中选取几道有代表性的题目，结合各题特性解题，从中找出一般规律，希望能起到抛砖引玉的作用。解决数列问题