斐波那契數

-{zh-hant:費波那契數;zh-hans:斐波那契數}-，又譯為菲波拿契數列、菲波那西數列、斐氏數列、黃金分割數列。這個數列是由義大利數學家斐波那契在他的《算盤書》中提出。在數學上，斐波那契數是以遞迴的方法來定義：用文字來說，就是斐波那契數列由0和1開始，之後的斐波那契數就是由之前的兩數相加而得出。首幾個斐波那契數是：987……特別指出：0不是第一項，而是第零項。起源.公元1150年印度數學家Gopala和金月在研究箱子包裝物件長寬剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是比薩的李奧納多，他描述兔子生長的數目時用上了這數列：假設在formula_5月有兔子總共formula_6對，formula_7月總共有formula_8對。在formula_9月必定總共有formula_10對：因為在formula_9月的時候，前一月。而新生育出的兔子對數等於所有在formula_5月就已存在的formula_6對斐波納契數也是楊輝三角的每一條紅色對角線上數字的和。表示式.為求得斐波那契數列的一般表示式，可以藉助線性代數的方法。高中的初等數學知識也能求出。初等代數解法.已知首先構建等比數列.設formula_20化簡得formula_21比較係數可得：formula_22不妨設formula_23解得：formula_24又因為有formula_20，即formula_26為等比數列。求出數列formula_27.由以上可得：formula_28變形得：formula_29。令formula_30求數列formula_31進而得到formula_32.formula_33設formula_34，解得formula_35。故數列formula_36為等比數列即formula_37。而formula_38，故有formula_39又有formula_24和formula_30可得formula_42得出formula_43表示式formula_42當formula_50時，formula_51，成立當formula_52時，formula_53，成立設當formula_54及formula_55時皆成立，即formula_56且formula_57當formula_58時formula_59亦成立當formula_50時，成立當formula_62時，formula_63，成立設當formula_64及formula_65時皆成立，即formula_66且formula_67當formula_68時formula_69亦成立用數學歸納法證明表示式.因此，根據數學歸納法原理，此表示式對於任意整數formula_5皆成立線性代數解法.formula_71formula_72構建一個矩陣方程.設formula_73為第formula_5個月有生育能力的兔子數量，formula_75為這一月份的兔子數量。formula_76上式表達了兩個月之間，兔子數目之間的關係。而要求的是，formula_77的表示式。求矩陣的特徵值：formula_78.根據特徵值的計算公式，我們需要算出來 formula_79 所對應的解。展開行列式有：formula_80。故當行列式的值為 0，解得 formula_81 或 formula_82。特徵向量.將兩個特徵值代入formula_83求特徵向量formula_84得formula_85=formula_86formula_87=formula_88分解首向量.第一個月的情況是兔子一對，新生0對。formula_89將它分解為用特徵向量表示。formula_90 用數學歸納法證明.從formula_91=formula_92可得到formula_93 化簡矩陣方程.將formula_94根據3formula_95求A的表示式.現在在6的基礎上，可以很快求出formula_77的表示式，將兩個特徵值代入6中formula_97formula_98formula_99即為formula_77的表示式數論解法.實際上，如果將斐波那契數列的通項公式寫成formula_101，即可利用解二階線性齊次遞迴關係式的方法，寫出其特徵多項式formula_102，然後解出formula_103=formula_104，formula_105=formula_106，即有formula_107，其中formula_108為常數。我們知道formula_109，因此formula_110，解得formula_111。組合數解法.formula_112formula_113黃金比例恆等式解法.設formula_46為黃金比例formula_47，則有恆等式formula_116與formula_117，其中formula_5為任意整數，則formula_119因此得到formula_120的一般式：formula_121此一般式對任意整數formula_5成立近似值.當formula_5為足夠大的正整數時，則formula_124formula_125用計算機求解.可透過程式設計觀察斐波那契數列。分為兩類問題，一種已知數列中的某一項，求序數。第二種是已知序數，求該項的值。可透過遞迴遞推的演算法解決此兩個問題。事實上當formula_5相當巨大的時候，O的遞推/遞迴非常慢……這時候要用到矩陣快速冪這一技巧，可以使遞迴加速到O(logn)。和黃金分割的關係.開普勒發現數列前、後兩項之比formula_127，也組成了一個數列，會趨近黃金分割：formula_128斐波那契數亦可以用連分數來表示：formula_129formula_130而黃金分割數亦可以用無限連分數表示：formula_131而黃金分割數也可以用無限多重根號表示：formula_132和自然的關係.斐氏數列見於不同的生物學現象，如樹的分枝、、菠蘿聚花果上小單果的排列、雅枝竹的花蕾、正在舒展的蕨葉、松毬的鱗的排列、蜜蜂的家族樹。開普勒曾指出斐氏數列存在於自然界，並以此解釋某些花的五邊形形態數通常為斐氏數。1830年，K. F. Schimper和A. Braun發現植物的旋生葉序中，連續兩塊葉之間轉過的角度與周角之比，約成整數比時，常出現斐氏數，如formula_133或formula_134。恆等式.證明以下的恆等式有很多方法。以下會用組合論述來證明。不失一般性，我們假設formula_137，formula_138是計算了將1和2加到n的方法的數目。若第一個被加數是1，有formula_120種方法來完成對formula_140的計算；若第一個被加數是2，有formula_141來完成對formula_142的計算。因此，共有formula_143種方法來計算n的值。計算用多個1和多個2相加令其和等於formula_7的方法的數目，同時至少一個加數是2的情況。如前所述，當formula_146，有formula_147種這樣的方法。因為當中只有一種方法不用使用2，就即formula_148　，於是我們從formula_147減去1。若該數式包含2為被加數，2的首次出現位置必然在第1和formula_7的被加數之間。2在不同位置的情況都考慮到後，得出formula_158為要求的數目。藉由上述公式，又可推得以下恆等式：formula_189數論性質.斐波那契質數.在斐波那契數列中，有質數：2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……截至2015年，已知最大的斐波那契質數是第104911個斐波那契數，一共有21925個十進位制位。不過，人們仍不知道是不是有無限個斐波那契質數。如所述，formula_190總能被formula_120整除，故除formula_192之外，任何斐氏質數的下標必同為質數。由於存在的一列連續合數，斐氏數列中亦能找到連續任意多項全為合數。大於formula_193的斐氏數，必不等於質數加一或減一。與其他數列的交集.斐波那契數列中，只有3個平方數：0、1、144。2001年，證明衹有有限多個斐氏數是完全冪。2006年，Y. Bugeaud、M. Mignotte、S. Siksek三人證明此種冪僅得0、1、8、144。1、3、21、55為僅有的斐氏三角形數。曾猜想此結論，後來由羅明證明。斐波那契數不能為完全數。推而廣之，除1之外，其他斐氏數皆非多重完全數，任兩個斐氏數之比亦不能是完全數。模"n"的週期性.斐波那契數列各項模formula_5的餘數構成，其最小正週期稱為皮薩諾週期，至多為formula_195。皮薩諾週期對不同formula_5值的通項公式仍是未解問題，其中一步需要求出某個整數或二次有限域元素的。不過，對固定的formula_5，求解模formula_5的皮薩諾週期是問題的特例。推廣.斐波那西數列是斐波那西n步數列步數為2的特殊情況，也和盧卡斯數列有關。formula_199反費波那西數列.反費波那西數列的遞迴公式如下：formula_200如果它以1,-1開始，之後的數是：1,-1,2,-3,5,-8, ...即是formula_201，亦可寫成formula_202，其中formula_185是非負整數。反費波那西數列兩項之間的比會趨近formula_204。證明關係式.證明formula_205，其中formula_185是非負整數以formula_46表示黃金分割數formula_47，則有formula_209故formula_210，因此formula_211巴都萬數列.費波那西數列可以用一個接一個的正方形來表現，巴都萬數列則是用一個接一個的等邊三角形來表現，它有formula_212的關係。佩爾數列.佩爾數列的遞迴公式為formula_213，前幾項為0,1,2,5,12,29,70,169,408...應用.1970年，尤裡·馬季亞謝維奇指出了偶角標的斐波那契函式formula_214正是滿足Julia Robison假設的丟番圖函式，因而證明瞭希爾伯特第十問題是不可解的。電腦科學.）版本用到斐氏數列，是將未排序的陣列分為兩份，長度為相鄰的斐氏數。《計算機程式設計藝術》描述了此種的實作方法，適用於以磁帶機為外存的情況。程式參考.JavaScript迭代版function fib(n) {var fib_n = function(curr, next, n) {if (n == 0) {return curr;else {return fib_n(next, curr+next, n-1);return fib_n(0, 1, n);alert(fib(40));C語言通項公式版int main()int n;double constant_a = (1 + sqrt(5)) / 2;double constant_b = (1 - sqrt(5)) / 2;double constant_c = sqrt(5) / 5;double value_1 = 0;int value_2 = 0;scanf("%d", &amp;n);if(n &gt; 0)for (int i = 0; i  0)for (unsigned long long i = 0; i &lt; n; i++)v1 = cc * (pow(ca, i) - pow(cb, i));v2 = (int)v1;cout «v2«endl;return 0;elsereturn -1;cout «'/b';Python語言通項公式版def fib(n): # write Fibonacci series up to na, b = 0, 1while b &lt; n:print(b, end=' ')a, b = b, a+bprint()def fib2(n): # return Fibonacci series up to nresult = []a, b = 0, 1while b &lt; n:result.append(b)a, b = b, a+breturn resultfibs = [0, 1]numZS = int(input('How many Fibonacci numbers do you want? '))for i in range(numZS-2):fibs.append(fibs[-2] + fibs[-1])print fibsCommon Lisp(cond ((equal x 0) 1)((equal x 1) 1)(t (+ (fibs (- x 1))(fibs (- x 2))))))(do ((n 0 (+ n 1))(i 1 j)(j 1 (+ i j)))((equal n x) i)))Go遞迴版，時間複雜度為 O(2^n)：func fibonacci(n int) int {if n &lt; 2 {return nreturn fibonacci(n-2) + fibonacci(n-1)通用版，時間複雜度為 O(n)：func fibonacci(n int) int {a, b := n%2, 1for i := 0; i &lt; n/2; i++ {a += bb += areturn aJava語言遞迴版：public int fibonacci(int n){if(n&lt;2){return n;}else {return fibonacci(n-1)+fibonacci(n-2);Java語言快捷版：public int fibonacci(int n){if(n&lt;2){return n;}else {int[] ans = new int[n];ans[0] = 1;ans[1] = 2;for(int i=2;i&lt;n;i++) {ans[i]=ans[i-1]+ans[i-2];return ans[n-1];C語言陣列版：int main()int n,s,L;printf("輸入長度");scanf("%d",&amp;L);while(L&lt;0)printf("錯誤");return 0;int a[L];int x=1,y=2;a[0]=x;a[1]=x;a[2]=y;for(n=3;n&lt;L;n++)a[n]=a[n-1]+a[n-2];for(n=0;n&lt;L;n++)printf("%d ",a[n]);system("pause");return 0;Python Lambda 遞迴版:fib = lambda n: n if n&lt;2 else fib(n-1) + fib(n-2)