I 編 號 ： _ 審定成績 ： _ 重 慶 郵 電 學(xué) 院 畢 業(yè) 設(shè) 計 （論 文） 設(shè)計（論文）題目 : 單位 (二級學(xué)院 )： 計算機科學(xué)與技術(shù)學(xué)院 學(xué) 生 姓 名 ： 專 業(yè) ： 信息與計算科學(xué) 班 級 ： 學(xué) 號 ： 指 導(dǎo) 教 師 ： 副教授 答辯組負(fù)責(zé)人 ： 填表時間： 2005 年 6 月 重慶郵電學(xué)院教務(wù)處制重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 列的研究 摘 要 列（斐波那契數(shù)列）起源于兔子繁殖問題，因而也叫兔子數(shù)列。這是一個很重要的遞推數(shù)列，受到了廣泛而深入的研究。本文系統(tǒng)地闡述了與列有關(guān)的若干問題。從數(shù)列的起源入手，給出了其一般的定義，然后又給出了三種更常用的表達(dá)式，包括直接求值形式、行列式形式和對分遞歸形式，從不同角度揭示了這個數(shù)列的本質(zhì)，并且，為下文的各種證明奠定的基礎(chǔ)。文章總結(jié)歸納證明了 20 多條 列的性質(zhì)，并且，由于引入了矩陣表達(dá)式，大大簡化了許多性質(zhì)的證明。同時，根據(jù)數(shù)列特點，文章大量采用歸納法，自成體系，論證嚴(yán)密。在給出了性質(zhì)之后，文章進(jìn)一步討論了該數(shù)列的應(yīng)用及推廣，涉及到利用 生成勾股數(shù)，利用遞推關(guān)系建立模型解題，定義了 列證明了點列的兩個性質(zhì)，引入了黃金分割的概念并闡述了其和 列的關(guān)系，還得到了一種比二分查找算法性能更優(yōu)的 其遞推關(guān)系的典型性，文章給出了求解 的若干算法并實現(xiàn)了它們，包括逐項遞歸算法、對分遞歸算法、逐項迭代算法、對分迭代算法和直接求值法。在結(jié)尾部分，文章還簡介了 列與自然界的聯(lián)系。 關(guān)鍵詞： 列 斐波那契數(shù)列 兔子數(shù)列 遞推 矩陣表達(dá)式 歸納法 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 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 慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 錄 前言 . 1 1 問題的提出 . 4 2 . 5 接求值形式 . 5 行列式形式 . 7 對分遞歸形式 . 9 3 若干性質(zhì) . 10 4 若干應(yīng)用與推廣 . 20 用 生成勾股數(shù) . 21 用 列 的遞推關(guān)系解題舉例 . 21 在幾何上的應(yīng)用：點列 . 22 列 與黃金分割 . 25 金分割簡介 . 25 黃金分割的關(guān)系 . 26 列 在算法上的應(yīng)用 . 27 法概述 . 27 例實現(xiàn) . 28 法性能 . 28 5 幾種求法及比較 . 29 項遞歸算法 . 29 分遞歸算法 . 29 項迭代算法 . 30 分迭代算法 . 30 接求值算法 . 31 6 結(jié)束語 . 31 致謝 . 33 參考文獻(xiàn) . 34 英文資料翻譯（原文） . 36 英文資料中文 . 57 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 1 前 言 由“兔子繁殖問題”而引出的 列，有著許多重要的、有趣的性質(zhì)。由于其理論嚴(yán)謹(jǐn)、邏輯推理周密以及應(yīng)用廣泛，引起了很多人的關(guān)注，包括各門學(xué)科的學(xué)者。 1963 年，美國數(shù)學(xué)會還專門出 版了季刊 當(dāng)然，也是對偉大的數(shù)學(xué)家 一種紀(jì)念。在國內(nèi)，天津商學(xué)院管理工程系吳振奎教授編著了斐波那契數(shù)列一書（世界數(shù)學(xué)名題欣賞從書），詳細(xì)清晰地闡述了 列的諸多性質(zhì)及應(yīng)用，周持中教授也出版了專著 、 及其應(yīng)用。 本文就是一篇關(guān)于 列的論文。文章內(nèi)容豐富，對 列的起源、表達(dá)方式、重要性質(zhì)、若干應(yīng)用及求解 的方法進(jìn)行了論述。 內(nèi)容上，文章分 成 6 個部分。 在第一部分，作者描述了 列的起源，引出了基本的定義。 在第二部分，作者論證了 列的三種表達(dá)方式，包括直接求值方式、行列式方式和對分遞歸方式。 在第三部分，作者列舉了 列一些常見重要的性質(zhì)，并進(jìn)行了證明。 在第四部分，作者列舉了 列的五個應(yīng)用，包括利用 及 列在幾何上、黃金分割上和算法上的應(yīng)用。 在第五部分，作者給出了求 的幾個算法并實現(xiàn)了它們，比較了它們的優(yōu)劣。其實現(xiàn)代碼都在 + 調(diào)試通過。 在第六部分，作者總結(jié)全文內(nèi)容，對 列與自然界的聯(lián)系做了簡要介紹。 在第二部分中，作者從幾個角度闡述了 列的本質(zhì)。其中定理 1給出了任意項 的算術(shù)通項，其重要意義不言而喻，事實上，下文的很多性質(zhì)都是通過它的直接代入來推導(dǎo)的，或者說，它提供了驗證一些等式的依重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 2 據(jù)，如性質(zhì) 8、性質(zhì) 12 等等。在定理 1 的證明中引入了 列的矩陣遞推式（ 這是一個令人激動的表達(dá) 式，用矩陣來研究數(shù)列將會帶來很多的方便，事實上，相對于許多資料上提供的方法來說，由于引入了（ 及其推導(dǎo)出來的矩陣表達(dá)式（ 本文的證明要簡潔得多。它的威力在定理 1 的證明中已有所體現(xiàn)，而在下文的很多定理、性質(zhì)都是由它而來，比如定理 3、推論 5、推論 6、推論 7 及性質(zhì) 11 和性質(zhì) 18 等。定理 3 的證明給 的求解提供了更快的途徑，第五部分的幾個算法就用到了它。性質(zhì) 11 是一個具有普遍意義的性質(zhì)，在性質(zhì) 18 的證明里起到了關(guān)鍵的作用。更為重要的，引入矩陣遞推式，給了 列賦予幾何 意義的手段！而諸多性質(zhì)可由（ 證明則暗示了其可能性。聯(lián)系定理 2，如果把 列和線性空間結(jié)合起來，相信將為 列以及線性空間的研究開辟廣闊的天地，這應(yīng)該會成為今后研究相關(guān)方面的一個方向。事實上，性質(zhì) 14 的幾何解釋、以及 關(guān)于點列的論述都在二維空間上印證了這一點，只是因為涉及到的只是少數(shù)幾個 而空間只是二維的。作者也相信，文中的絕大多數(shù)性質(zhì)都可以找到幾何解釋。 研究的對象是整數(shù)，整數(shù)有著其獨特的性質(zhì)，也有著其獨特的研究方法。首先，質(zhì) 15、 16、 17、 18、 19 都是關(guān)于這個特殊整數(shù)序列的描述。其次， n 是非負(fù)整數(shù)，并且組成一個等差數(shù)列，作為歸納法提供了方便。本文大量采用了歸納的思想，性質(zhì) 7、 13、 15、 16、 18 都是用歸納法證明的，而性質(zhì) 17 和性質(zhì) 19 的證明本質(zhì)上也是歸納。 列是一個很重要的遞推關(guān)系，從它暗合了很多自然現(xiàn)象就可以看出，應(yīng)用它可以解決很多問題。在文章的第四部分簡單的列舉了其幾種應(yīng)用。在計算機科學(xué) 里這是個很著名的數(shù)列，大約因為兩點，其一是應(yīng)用它建立的模型巧妙地簡化了很多問題，其二就是求解它的遞歸和迭代算法很具典型，正如第五部分所述。 文中的各個知識點大都散見于各種雜志，作者在整理的基礎(chǔ)上對很多性質(zhì)給予了獨特的證明和推廣，下面略作說明。定理 1，也就是 式 ，林全文老師的 的另兩個證明及其性質(zhì) 及 盧開澄 老師 的組合數(shù)學(xué) 上面采用的都是生成函數(shù)的方法來證明的，這是研究遞推關(guān)系最普遍的方法，作者引重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 3 入矩陣遞推式（ 從另一個角度進(jìn)行了證明。而正因為如此，使得定理 3 得以證明，作 者在很多介紹 列和算法的文章中看到此式，但沒見到一個證明，同時，性質(zhì) 11 也是受到這里的啟發(fā)才得以證明的。 孔慶新 老師在 的若干性質(zhì)（ 一文中對性質(zhì) 5、 6、 7、 10 進(jìn)行了證明了，本文采用了不同的方法，更重要的是，更正了孔先生對性質(zhì) 7 證明的錯誤，在孔先生的證明中，混淆了奇偶的區(qū)別。而對于開普勒公式（推論 4），作者巧妙的將其作為性質(zhì) 8 的一個特例！對于推論 6、 7 和性質(zhì) 9， 宋長新 老師在 列的若干性質(zhì)都有證明，但都是引入了 列才 得以解決，本文的證法也與之不同。此外，性質(zhì) 13、 17、 18、 19 以及定理 5 等完全是作者獨立證明。 豐富的知識加上合理清晰的數(shù)學(xué)思想，成就了這篇文章。 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 4 1 問題的提出 13世紀(jì)意大利著名數(shù)學(xué)家斐波那契 (他的著作算盤書 (，記載著這樣一個有趣的問題：“由一對兔子開始，一年 后可以繁殖成多少對兔子？”假設(shè)免子的生殖力是這樣的：每對兔子每一個 月可以生一對兔子，并且兔子在出生兩個月后就具有生殖后代的能力，逐月 登記兔子 的對數(shù)： 第 0個月末（即初始時，第一個月初）：有 1對兔子； 第一個月末：有 1對兔子； 第二個月末：前一對兔子有了繁殖能力，并生下一對兔子，有 2對兔子； 第三個月末：第一月末時的兔子繁殖了 1對兔子，加上第二個月本來有 的兔子，是 3對兔子； 第四個月末：第二個月末的兔子繁殖了 2對兔子，加上第三個月本來有 的兔子，是 5對兔子； 第 上第 n 個月本來有的兔子，總共就是前兩個月末兔子數(shù)之和； 于是可得如下的數(shù)列 : 02F 35 1 1 2 3 5 8 13 1列。 定義 134 稱數(shù)列 （ n=0,1,2）為 列，如果滿足： 0F=1， 1F =1， 并且， 2nF+ n=0,1,2 （ 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 5 其中任意一個數(shù)。 如植物的枝干與葉子的生長等 )有緊密的聯(lián)系。它在純數(shù)學(xué)領(lǐng)域的一個極為成功的應(yīng)用是幫助數(shù)學(xué)家馬蒂雅舍維奇解決了著名的 最終判定 外，它在人口理論、對策論、最優(yōu)化理論、層次分析、運籌學(xué)等領(lǐng)域都有十分廣泛的應(yīng)用。 2 列表達(dá)式的探求 列是二階遞歸數(shù)列，它有初始值 1、 1，從第三個數(shù)開始，每個數(shù)是前兩個數(shù)之和：2nF+n=0,1,2 ，這種定義叫做遞歸定義，具有很強的直觀性，但不利于通項的計算，下面我們來推導(dǎo) 接求值形式 定理 135 若設(shè)2 511 ， 2 512 ， 則 列具有通項如下： 121151 ， n=0,1,2 （ 下面來推導(dǎo)。 從高等的觀點來說，遞歸公式和通項公式之間存在著必然的聯(lián)系。由于這是二階遞歸數(shù)列，所以其矩陣系數(shù)為二階方陣。即： 1 0111 21,3,4 （ 6 令 1A = 0111，則上式化為 12A23A3 = 1f ， 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 6 其中 1f = 0111。 因此，我們只需要求出 1可求出 項。 2 很顯然， A 可相似對角化，下面我們先求解 A 的特征值和特征向量。 012 解得特征值： 2 511 ， 2 512 。 對應(yīng)的特征向量分別為： 2112511， 1212511。 所以， 1A ，其中， 25112511111221 ， 21 ， 11251251511151211 。 由此， 1 11 n ， 1f = 1111115121121112 121211212112112151 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 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)(，（ 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 8 引理 1：)(10000100100=.,)1(.,11 列展開，得到遞推公式 + )12 即： (1 遞推下去得到 2k ( 2D - 1D )， 又： 1D = + ， 2D =( + )2 - ， 所以，2k ( 2D - 1D ) = 2k ( + )2 - - ( + ) = k 即k （ 交換 和 ， k （ 當(dāng) 時，聯(lián)立兩式解出有 11 當(dāng) 時，對（ 遞推得到 k +1 = 2)2( k + 2k 2D 即 )1( . 引理得證。 對定理 2 來說，在引理中的 , 滿足： 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 9 + =1, = 即 , 是方程 012 兩個根。 若設(shè) ，則 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 為偶數(shù) （ 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 10 )(12/)1(12/)1(2/)1( ，且 n 為奇數(shù) 證明：約定 1F =0， 由（ 有 11 0111 1 1 0111 21 可得到下列遞推矩陣關(guān)系式： 11 nn F 01 11 21 1nn F n 01 11 10 01 F= 10111 n 令 A = 01 11，則 11 nn F 1 （ 當(dāng) n=0,1 時，. 當(dāng) n1 時， 122 212 kk F 12 1kA = 11 kk F 21 1kk F )()( 21212 11211 對比等式兩邊矩陣，即有 1122122 )(1112 即證得（ 。 3 列的若干性質(zhì) 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 11 性質(zhì) 118 nk F+ 1F + +12 證明： 120 231 1)21012 性質(zhì) 218 nk =0F+ 2F + +2證明： 10 32 1222012122) 性質(zhì) 318 nk 2= 1F +3F+ +1212 證明：綜合性質(zhì) 1 和性質(zhì) 2 即可得到性質(zhì) 3. 性質(zhì) 418 nk 20F + 21F + + 2 1 證明： 20F=01 )(021 = 2112212011112 )()質(zhì) 59 nk ( = 0F + 12F + + 1( = 212 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 12 證明： 120 )(22231 2)1()1()2()1()()1(2)(1()1)(1221221211012 性質(zhì) 69 nk = 0 1)1( + + )3(3 證明：綜 合性質(zhì) 5 和性質(zhì) 1 即可證得。 性質(zhì) 79 nk 為偶數(shù)為奇數(shù)11 .（ m 為一給定正整數(shù)） 證明：用歸納法證明，分兩種情況。 當(dāng) n 為奇數(shù)時， n=1，即1 1 立。 假設(shè) 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，成立。 當(dāng) n 為偶數(shù)時， n=0，即立。 假設(shè) n=2p 時成立，即 pk = F 212 ， 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 13 則 n=2p+2 時， 220pk F 212 + F 1212 + F 2222 = )(12212 +F 2222=222212 )( FF=F 2232，成立。 即性質(zhì) 7 得證。 推論 1 nk =為偶數(shù)為奇數(shù)112 . 證明：在性質(zhì) 7 中令 m=1 即證。 推論 2 nk =為偶數(shù)為奇數(shù)213 . 證明：在性質(zhì) 7 中令 m=2 即證。 推論 3 nk 1=為偶數(shù)為奇數(shù)211 . 證明：這就是推論 2 的另一種表達(dá)形式而已。 性質(zhì) 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( . 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 14 推論 4 21 F= n)1( . 證明：在性質(zhì) 8 中，令 k=1 即可。 推論 5 F 11 F=)1(2)1( . 證明：根據(jù)性質(zhì) 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 性質(zhì) 911 11 F= 1)1( n . 證明：11 F=1)( 11 21 1 )( ( 21 F) 而根據(jù)推論 4 21 F= n)1( 所以，11 F= 1)1( n . 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 15 性質(zhì) 109 nk 0 1 n)1(121 . 證明：根據(jù)性質(zhì) 4 有： nk 20F + 21F + + 2 1而由推論 3 有： nk 1=為偶數(shù)為奇數(shù)211 上兩式相減， n 為奇數(shù)時， nk 0 1 0. n 為偶數(shù)時，根據(jù)性質(zhì) 9， nk 10 1 k 12 F = 1)1()1( n =1. 即 nk 0 1 n)1(121 . 性質(zhì) 1110 3,2,1,(,11 證明：根據(jù)（ 11 nn F 10111 n 則有 F 12= 20111 = 10111 n 10111 m = 11 nn F 11 mm F 1111 1111 應(yīng)元素得： 3,2,1,(,11 這是一個很有用的通用表達(dá)式，事實上，上文定理 3 的遞歸迭代表重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 16 達(dá)式（ 是此性質(zhì)的特殊情形。 性質(zhì) 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. 得證。 性質(zhì) 138 1111111個n. 證明：用 歸納法證明。 當(dāng) n=0 時，01， 假設(shè)當(dāng) n=k 時成立，即 1111111個k， 當(dāng) n=k+1 時，12+ 1+ 1211111個k，成立。 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 17 所以，對任意 n， 1111111個 性質(zhì) 145 221 nF 證明： 3nF )(12 F )( 12 F= 221 下圖： 在圓 O 中，由圓冪定理有 2 而由勾股定理有 22 則 22 = 設(shè)圓 O 半徑為 R，令 1，C ， 則 2 ，3 式子 22 = 即性質(zhì) 14。 性質(zhì) 158 任意 相隔 10項的兩個 F 10=11q， n 0. 證明：記F 10，用歸納法證明。 當(dāng) n=0時，0F=010 =88，成立。 當(dāng) n=1時， 1F = 111 =143，成立。 假設(shè)當(dāng) n=k,n= 即F 10=11 19 F=111kq， 重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 18 當(dāng) n=k+1時，111 F=F 10+19 F=11( 所以，原命題成立。 性質(zhì) 168 任意連續(xù) 10 個 之和是 11 的倍數(shù)。 證明：記nS= +90n ，即證 1nq， 當(dāng) n=0時，0S=143，成立。 當(dāng) n=1時， 1S =231，成立。 假設(shè)當(dāng) n= 即kS= +91kq， 當(dāng) n=k+1時，1 +10kF= +90kF 110kF 根據(jù)性質(zhì) 15，10kF 是 11的倍數(shù)。 所以，原命題成立。 性質(zhì) 178 ,1，即相鄰的 互為素數(shù)。（ ,M)表示 N、 M 的最大公約數(shù)） 證明：用 (N )表示 N 除以 M 的余數(shù)， 當(dāng) n0 時，2nF+且1nF 所以121 因此，對任意 k0， (2 , =,重慶郵電學(xué)院本科畢業(yè) 設(shè)計 (論文 ) 19 = =,2F 1F )=1. 同時， ,0F 1F)=1. 所以 相鄰的 互為素數(shù)。 性質(zhì) 188 對于非負(fù)整數(shù) 1n 2