【毕业学位论文】（Word原稿）Fibonacci（斐波那契数列）数列的研究-信息与计算科学

I 编 号 ： _ 审定成绩 ： _ 重 庆 邮 电 学 院 毕 业 设 计 （论 文） 设计（论文）题目 : 单位 (二级学院 )： 计算机科学与技术学院 学 生 姓 名 ： 专 业 ： 信息与计算科学 班 级 ： 学 号 ： 指 导 教 师 ： 副教授 答辩组负责人 ： 填表时间： 2005 年 6 月 重庆邮电学院教务处制重庆邮电学院本科毕业 设计 (论文 ) 列的研究 摘 要 列（斐波那契数列）起源于兔子繁殖问题，因而也叫兔子数列。这是一个很重要的递推数列，受到了广泛而深入的研究。本文系统地阐述了与列有关的若干问题。从数列的起源入手，给出了其一般的定义，然后又给出了三种更常用的表达式，包括直接求值形式、行列式形式和对分递归形式，从不同角度揭示了这个数列的本质，并且，为下文的各种证明奠定的基础。文章总结归纳证明了 20 多条 列的性质，并且，由于引入了矩阵表达式，大大简化了许多性质的证明。同时，根据数列特点，文章大量采用归纳法，自成体系，论证严密。在给出了性质之后，文章进一步讨论了该数列的应用及推广，涉及到利用 生成勾股数，利用递推关系建立模型解题，定义了 列证明了点列的两个性质，引入了黄金分割的概念并阐述了其和 列的关系，还得到了一种比二分查找算法性能更优的 其递推关系的典型性，文章给出了求解 的若干算法并实现了它们，包括逐项递归算法、对分递归算法、逐项迭代算法、对分迭代算法和直接求值法。在结尾部分，文章还简介了 列与自然界的联系。 关键词： 列 斐波那契数列 兔子数列 递推 矩阵表达式 归纳法 重庆邮电学院本科毕业 设计 (论文 ) f is it a of is a an of a It of of of of of of of a of to of is to a of of is to of of to by by a is as to 庆邮电学院本科毕业 设计 (论文 ) 录 前言 . 1 1 问题的提出 . 4 2 . 5 接求值形式 . 5 行列式形式 . 7 对分递归形式 . 9 3 若干性质 . 10 4 若干应用与推广 . 20 用 生成勾股数 . 21 用 列 的递推关系解题举例 . 21 在几何上的应用：点列 . 22 列 与黄金分割 . 25 金分割简介 . 25 黄金分割的关系 . 26 列 在算法上的应用 . 27 法概述 . 27 例实现 . 28 法性能 . 28 5 几种求法及比较 . 29 项递归算法 . 29 分递归算法 . 29 项迭代算法 . 30 分迭代算法 . 30 接求值算法 . 31 6 结束语 . 31 致谢 . 33 参考文献 . 34 英文资料翻译（原文） . 36 英文资料中文 . 57 重庆邮电学院本科毕业 设计 (论文 ) 1 前 言 由“兔子繁殖问题”而引出的 列，有着许多重要的、有趣的性质。由于其理论严谨、逻辑推理周密以及应用广泛，引起了很多人的关注，包括各门学科的学者。 1963 年，美国数学会还专门出 版了季刊 当然，也是对伟大的数学家 一种纪念。在国内，天津商学院管理工程系吴振奎教授编著了斐波那契数列一书（世界数学名题欣赏从书），详细清晰地阐述了 列的诸多性质及应用，周持中教授也出版了专著 、 及其应用。 本文就是一篇关于 列的论文。文章内容丰富，对 列的起源、表达方式、重要性质、若干应用及求解 的方法进行了论述。 内容上，文章分 成 6 个部分。 在第一部分，作者描述了 列的起源，引出了基本的定义。 在第二部分，作者论证了 列的三种表达方式，包括直接求值方式、行列式方式和对分递归方式。 在第三部分，作者列举了 列一些常见重要的性质，并进行了证明。 在第四部分，作者列举了 列的五个应用，包括利用 及 列在几何上、黄金分割上和算法上的应用。 在第五部分，作者给出了求 的几个算法并实现了它们，比较了它们的优劣。其实现代码都在 + 调试通过。 在第六部分，作者总结全文内容，对 列与自然界的联系做了简要介绍。 在第二部分中，作者从几个角度阐述了 列的本质。其中定理 1给出了任意项 的算术通项，其重要意义不言而喻，事实上，下文的很多性质都是通过它的直接代入来推导的，或者说，它提供了验证一些等式的依重庆邮电学院本科毕业 设计 (论文 ) 2 据，如性质 8、性质 12 等等。在定理 1 的证明中引入了 列的矩阵递推式（ 这是一个令人激动的表达 式，用矩阵来研究数列将会带来很多的方便，事实上，相对于许多资料上提供的方法来说，由于引入了（ 及其推导出来的矩阵表达式（ 本文的证明要简洁得多。它的威力在定理 1 的证明中已有所体现，而在下文的很多定理、性质都是由它而来，比如定理 3、推论 5、推论 6、推论 7 及性质 11 和性质 18 等。定理 3 的证明给 的求解提供了更快的途径，第五部分的几个算法就用到了它。性质 11 是一个具有普遍意义的性质，在性质 18 的证明里起到了关键的作用。更为重要的，引入矩阵递推式，给了 列赋予几何 意义的手段！而诸多性质可由（ 证明则暗示了其可能性。联系定理 2，如果把 列和线性空间结合起来，相信将为 列以及线性空间的研究开辟广阔的天地，这应该会成为今后研究相关方面的一个方向。事实上，性质 14 的几何解释、以及 关于点列的论述都在二维空间上印证了这一点，只是因为涉及到的只是少数几个 而空间只是二维的。作者也相信，文中的绝大多数性质都可以找到几何解释。 研究的对象是整数，整数有着其独特的性质，也有着其独特的研究方法。首先，质 15、 16、 17、 18、 19 都是关于这个特殊整数序列的描述。其次， n 是非负整数，并且组成一个等差数列，作为归纳法提供了方便。本文大量采用了归纳的思想，性质 7、 13、 15、 16、 18 都是用归纳法证明的，而性质 17 和性质 19 的证明本质上也是归纳。 列是一个很重要的递推关系，从它暗合了很多自然现象就可以看出，应用它可以解决很多问题。在文章的第四部分简单的列举了其几种应用。在计算机科学 里这是个很著名的数列，大约因为两点，其一是应用它建立的模型巧妙地简化了很多问题，其二就是求解它的递归和迭代算法很具典型，正如第五部分所述。 文中的各个知识点大都散见于各种杂志，作者在整理的基础上对很多性质给予了独特的证明和推广，下面略作说明。定理 1，也就是 式 ，林全文老师的 的另两个证明及其性质 及 卢开澄 老师 的组合数学 上面采用的都是生成函数的方法来证明的，这是研究递推关系最普遍的方法，作者引重庆邮电学院本科毕业 设计 (论文 ) 3 入矩阵递推式（ 从另一个角度进行了证明。而正因为如此，使得定理 3 得以证明，作 者在很多介绍 列和算法的文章中看到此式，但没见到一个证明，同时，性质 11 也是受到这里的启发才得以证明的。 孔庆新 老师在 的若干性质（ 一文中对性质 5、 6、 7、 10 进行了证明了，本文采用了不同的方法，更重要的是，更正了孔先生对性质 7 证明的错误，在孔先生的证明中，混淆了奇偶的区别。而对于开普勒公式（推论 4），作者巧妙的将其作为性质 8 的一个特例！对于推论 6、 7 和性质 9， 宋长新 老师在 列的若干性质都有证明，但都是引入了 列才 得以解决，本文的证法也与之不同。此外，性质 13、 17、 18、 19 以及定理 5 等完全是作者独立证明。 丰富的知识加上合理清晰的数学思想，成就了这篇文章。 重庆邮电学院本科毕业 设计 (论文 ) 4 1 问题的提出 13世纪意大利著名数学家斐波那契 (他的著作算盘书 (，记载着这样一个有趣的问题：“由一对兔子开始，一年 后可以繁殖成多少对兔子？”假设免子的生殖力是这样的：每对兔子每一个 月可以生一对兔子，并且兔子在出生两个月后就具有生殖后代的能力，逐月 登记兔子 的对数： 第 0个月末（即初始时，第一个月初）：有 1对兔子； 第一个月末：有 1对兔子； 第二个月末：前一对兔子有了繁殖能力，并生下一对兔子，有 2对兔子； 第三个月末：第一月末时的兔子繁殖了 1对兔子，加上第二个月本来有 的兔子，是 3对兔子； 第四个月末：第二个月末的兔子繁殖了 2对兔子，加上第三个月本来有 的兔子，是 5对兔子； 第 上第 n 个月本来有的兔子，总共就是前两个月末兔子数之和； 于是可得如下的数列 : 02F 35 1 1 2 3 5 8 13 1列。 定义 134 称数列 （ n=0,1,2）为 列，如果满足： 0F=1， 1F =1， 并且， 2nF+ n=0,1,2 （ 重庆邮电学院本科毕业 设计 (论文 ) 5 其中任意一个数。 如植物的枝干与叶子的生长等 )有紧密的联系。它在纯数学领域的一个极为成功的应用是帮助数学家马蒂雅舍维奇解决了著名的 最终判定 外，它在人口理论、对策论、最优化理论、层次分析、运筹学等领域都有十分广泛的应用。 2 列表达式的探求 列是二阶递归数列，它有初始值 1、 1，从第三个数开始，每个数是前两个数之和：2nF+n=0,1,2 ，这种定义叫做递归定义，具有很强的直观性，但不利于通项的计算，下面我们来推导 接求值形式 定理 135 若设2 511 ， 2 512 ， 则 列具有通项如下： 121151 ， n=0,1,2 （ 下面来推导。 从高等的观点来说，递归公式和通项公式之间存在着必然的联系。由于这是二阶递归数列，所以其矩阵系数为二阶方阵。即： 1 0111 21,3,4 （ 6 令 1A = 0111，则上式化为 12A23A3 = 1f ， 重庆邮电学院本科毕业 设计 (论文 ) 6 其中 1f = 0111。 因此，我们只需要求出 1可求出 项。 2 很显然， A 可相似对角化，下面我们先求解 A 的特征值和特征向量。 012 解得特征值： 2 511 ， 2 512 。 对应的特征向量分别为： 2112511， 1212511。 所以， 1A ，其中， 25112511111221 ， 21 ， 11251251511151211 。 由此， 1 11 n ， 1f = 1111115121121112 121211212112112151 重庆邮电学院本科毕业 设计 (论文 ) 7 = ， 其中，用到 1121 ， 1222 。 即有， 121151 ， n=0,1,2 这就是闻名的 式。 事实上， 0F= 121151 =1， 1F = 222151 =1， 由于 1121 ， 1222 ， 121151 + 222151 = 2212211151 = )1()1(51212111 323151 = 2 即，列。 行列式形式 定理 2717 列的通项可用如下 n 阶行列式表示： 011000101100111001101)(，（ 重庆邮电学院本科毕业 设计 (论文 ) 8 引理 1：)(10000100100=.,)1(.,11 列展开，得到递推公式 + )12 即： (1 递推下去得到 2k ( 2D - 1D )， 又： 1D = + ， 2D =( + )2 - ， 所以，2k ( 2D - 1D ) = 2k ( + )2 - - ( + ) = k 即k （ 交换 和 ， k （ 当 时，联立两式解出有 11 当 时，对（ 递推得到 k +1 = 2)2( k + 2k 2D 即 )1( . 引理得证。 对定理 2 来说，在引理中的 , 满足： 重庆邮电学院本科毕业 设计 (论文 ) 9 + =1, = 即 , 是方程 012 两个根。 若设 ，则 2 51， 2 512 。 代入有 1151 ，此即（ 。 所以，定理 2 得证。 事实上，0F=1， 1F =1， 2F =1111 =2, )2()2(2110001011001110011=)1()1(11000101100111011+)1()1(110001011001100011=)(110001011001110011+)1()1(11000101100111001=即，列。 对分递归形式 定理 3 1， n=0,1 212/22/ ，且 n 为偶数 （ 重庆邮电学院本科毕业 设计 (论文 ) 10 )(12/)1(12/)1(2/)1( ，且 n 为奇数 证明：约定 1F =0， 由（ 有 11 0111 1 1 0111 21 可得到下列递推矩阵关系式： 11 nn F 01 11 21 1nn F n 01 11 10 01 F= 10111 n 令 A = 01 11，则 11 nn F 1 （ 当 n=0,1 时，. 当 n1 时， 122 212 kk F 12 1kA = 11 kk F 21 1kk F )()( 21212 11211 对比等式两边矩阵，即有 1122122 )(1112 即证得（ 。 3 列的若干性质 重庆邮电学院本科毕业 设计 (论文 ) 11 性质 118 nk F+ 1F + +12 证明： 120 231 1)21012 性质 218 nk =0F+ 2F + +2证明： 10 32 1222012122) 性质 318 nk 2= 1F +3F+ +1212 证明：综合性质 1 和性质 2 即可得到性质 3. 性质 418 nk 20F + 21F + + 2 1 证明： 20F=01 )(021 = 2112212011112 )()质 59 nk ( = 0F + 12F + + 1( = 212 重庆邮电学院本科毕业 设计 (论文 ) 12 证明： 120 )(22231 2)1()1()2()1()()1(2)(1()1)(1221221211012 性质 69 nk = 0 1)1( + + )3(3 证明：综 合性质 5 和性质 1 即可证得。 性质 79 nk 为偶数为奇数11 .（ m 为一给定正整数） 证明：用归纳法证明，分两种情况。 当 n 为奇数时， n=1，即1 1 立。 假设 n=2p+1 时成立，即 12 0pk F = F 2212 ， 则 n=2p+3 时， 32 0pk F = F 2212 + F 2222 + F 3232 = 222212 )(+ 3232= )(322232 =F 4232，成立。 当 n 为偶数时， n=0，即立。 假设 n=2p 时成立，即 pk = F 212 ， 重庆邮电学院本科毕业 设计 (论文 ) 13 则 n=2p+2 时， 220pk F 212 + F 1212 + F 2222 = )(12212 +F 2222=222212 )( FF=F 2232，成立。 即性质 7 得证。 推论 1 nk =为偶数为奇数112 . 证明：在性质 7 中令 m=1 即证。 推论 2 nk =为偶数为奇数213 . 证明：在性质 7 中令 m=2 即证。 推论 3 nk 1=为偶数为奇数211 . 证明：这就是推论 2 的另一种表达形式而已。 性质 8 2nF F = 211)1( . 证明：由定理 1 2 2121151 F = 121151 1211 上两式相减：注意到 21 = 1 ， 2nF F = )2()(51 2121121 = )(2)1(51 2122211 = 2211 )()1(51 = 2211 )()1(51 = 211)1( . 重庆邮电学院本科毕业 设计 (论文 ) 14 推论 4 21 F= n)1( . 证明：在性质 8 中，令 k=1 即可。 推论 5 F 11 F=)1(2)1( . 证明：根据性质 8，有 21 F = 22)1( 2nF F = 211)1( 上两式相减，有 F 11 F= )()1( 2122 F=)1(2)1( （定理 3） . 推论 611 2222 F 21212 F. 证明：在推论 5 F 11 F=)1(2)1( 中， 取 k=2，同时用 2n 代替 n，则有 2222 F ( 2221212 11 22 F F )1(211 . 证明：在推论 5 F 11 F=)1(2)1( 中， 取 k=2，则有22 F .)1(2)1( 2211 性质 911 11 F= 1)1( n . 证明：11 F=1)( 11 21 1 )( ( 21 F) 而根据推论 4 21 F= n)1( 所以，11 F= 1)1( n . 重庆邮电学院本科毕业 设计 (论文 ) 15 性质 109 nk 0 1 n)1(121 . 证明：根据性质 4 有： nk 20F + 21F + + 2 1而由推论 3 有： nk 1=为偶数为奇数211 上两式相减， n 为奇数时， nk 0 1 0. n 为偶数时，根据性质 9， nk 10 1 k 12 F = 1)1()1( n =1. 即 nk 0 1 n)1(121 . 性质 1110 3,2,1,(,11 证明：根据（ 11 nn F 10111 n 则有 F 12= 20111 = 10111 n 10111 m = 11 nn F 11 mm F 1111 1111 应元素得： 3,2,1,(,11 这是一个很有用的通用表达式，事实上，上文定理 3 的递归迭代表重庆邮电学院本科毕业 设计 (论文 ) 16 达式（ 是此性质的特殊情形。 性质 128 22=证明：由定 理 1 121151 ，则 2 2121151 ， 2 2121151 ， 上两式相减，有 22= )1(22)1(22)1(21)1(2151 . 同样， 12212112212151 = )1(22122121122121)1(2151 = )1(22)1(22)1(21)1(2151 = 22. 得证。 性质 138 1111111个n. 证明：用 归纳法证明。 当 n=0 时，01， 假设当 n=k 时成立，即 1111111个k， 当 n=k+1 时，12+ 1+ 1211111个k，成立。 重庆邮电学院本科毕业 设计 (论文 ) 17 所以，对任意 n， 1111111个 性质 145 221 nF 证明： 3nF )(12 F )( 12 F= 221 下图： 在圆 O 中，由圆幂定理有 2 而由勾股定理有 22 则 22 = 设圆 O 半径为 R，令 1，C ， 则 2 ，3 式子 22 = 即性质 14。 性质 158 任意 相隔 10项的两个 F 10=11q， n 0. 证明：记F 10，用归纳法证明。 当 n=0时，0F=010 =88，成立。 当 n=1时， 1F = 111 =143，成立。 假设当 n=k,n= 即F 10=11 19 F=111kq， 重庆邮电学院本科毕业 设计 (论文 ) 18 当 n=k+1时，111 F=F 10+19 F=11( 所以，原命题成立。 性质 168 任意连续 10 个 之和是 11 的倍数。 证明：记nS= +90n ，即证 1nq， 当 n=0时，0S=143，成立。 当 n=1时， 1S =231，成立。 假设当 n= 即kS= +91kq， 当 n=k+1时，1 +10kF= +90kF 110kF 根据性质 15，10kF 是 11的倍数。 所以，原命题成立。 性质 178 ,1，即相邻的 互为素数。（ ,M)表示 N、 M 的最大公约数） 证明：用 (N )表示 N 除以 M 的余数， 当 n0 时，2nF+且1nF 所以121 因此，对任意 k0， (2 , =,重庆邮电学院本科毕业 设计 (论文 ) 19 = =,2F 1F )=1. 同时， ,0F 1F)=1. 所以 相邻的 互为素数。 性质 188 对于非负整数 1n 2