Fibonacci 數列及其計算方法

斐波那契數列（Fibonacci sequence），又稱黃金分割數列，這個數列最早是由印度數學家提出來的。不過更多的人學習到這個數列是因為意大利數學家列昂納多·斐波那契（Leonardoda Fibonacci）和他的《Liber Abaci》一書。在這本書中，列昂納多·斐波那契以兔子繁殖為例子引出了這個序列，因此這個序列又稱為“兔子數列”。
這個序列的前幾項是這樣的：0,1,1,2,3,5,8,13,21,34,?
在數學上，斐波納契數列以如下被以遞歸的方法定義：

F(0)=0F(1)=1F(n)=F(n?1)+F(n?2)?,(n≥2,n∈N)

Fibonacci 數列的通項公式

Fibonacci 數列除了遞歸形式之外，當然還可以寫出通項公式。下面就來算算 F(n)。

F(n)=F(n?1)+F(n?2)
是典型的線性差分方程，可以用經典的待定系數法來解，當然也可以用 Z 變換解。考慮到不是每個人都學過 Z 變換，這里就給個最基本的待定系數法。假設 F(n)=C×Wn， C 和 W 是兩個待定系數，那么有：
Wn=Wn?1+Wn?2
化簡一下，得到：
W2=W+1
很顯然， W 有兩個解：
W1=1?5√2≈?0.618,W2=1+5√2≈1.618

那么 F(n)=C1Wn1+C2Wn2 也滿足 F(n)=F(n?1)+F(n?2)。
C1,C2 可以通過起始條件來確定。

F(0)=0=C1+C2F(1)=1=C1W1+C2W2
這是一個簡單的二元一次方程，計算后可以得到：
C1=?5√5,C2=5√5

所以：

F(n)=?5√51?5√2n+5√51+5√2n

當 n 較大時，C1Wn1=?0.4472×(?0.618)n≈0
所以 n 較大時，
F(n)≈5√51+5√2n≈0.4472×1.618n

有些沒有學過差分方程理論的同學可能會問為什么假設 F(n)=C×Wn。簡單的說，這是猜的。當然也不是無緣無故的猜測。我們知道 F(n) 的差分方程是這樣的：

F(n)=F(n?1)+F(n?2)
我們再構造兩個輔助的差分方程：

F1(n)=2F1(n?1)F2(n)=2F2(n?2)

那么當起始條件相同時，明顯有 F2(n)<F(n)<F1(n)。
F1(n),F2(n) 都是等比數列，通項公式如下：

F1(n)=2nC1F2(n)=2√nC2

所以 2√nC2<F(n)<2nC1。
所以我們猜測 F(n)=Wn，其中 2√<W<2。

程序實現

斐波納契數列的定義是遞歸形式的。自然，用遞歸函數最容易實現。

uint64_t Fibonacci(unsigned char n) {if( n == 0 ) return 0;if( n == 1 ) return 1;return Fibonacci(n - 1) + Fibonacci(n - 2); }

這個代碼雖然簡單，但是計算復雜度卻太高。當 n 稍微大一點時，計算時間就會非常長。

我們可以簡單的算一下，當計算 F(n) 時，F(n) 內部會調用 2+F(n?1)+F(n?2) 次自己。

我們用 B(n) 表示 F(n) 中多少次調用自己。那么就有遞歸表達式：

B(0)=0B(1)=0B(n)=2+B(n?1)+B(n?2)

那么這個 B(n) 具體是多少呢？ 顯而易見，當 n≥2 時，B(n)≥F(n)。

我們又知道 F(n)<B(n)<2F(n)，所以遞歸算法的時間復雜度是 O(1.618n)。1.618100=7.90409×1020。也就是說當 n=100 時，遞歸函數要反復調用自己 1020 次左右，這個計算時間是不能忍受的。

如果將遞歸算法改為遞推，時間復雜度會降低很多。

uint64_t Fibonacci(unsigned char n) {if( n == 0 ) return 0;if( n == 1 ) return 1;uint64_t fn, fnn = 1, fnnn = 0;for(int i = 2; i <= n; i ++){fn = fnn + fnnn;fnn = fn;fnnn = fnn;}return fn; }

這個程序很簡答，for 循環中計算了n?2 次， 所以時間復雜度為 O(n)。

那么原來的遞歸算法就沒有改進的余地了嗎？遞歸算法之所以算的慢，是因為計算F(n) 時，對于小于 n 的數 m，重復計算了很多次F(m)。下面這幅圖給出了計算 F(6) 時的遞歸調用關系。

可以看到 F(4),F(3) 都重復計算了好幾遍。其實，只要將計算過的F(m) 保存下來，下次用時直接讀取就好了，這樣就省去了反復計算 F(m) 的問題。下面是改進后的代碼，時間復雜度降低為 O(n)：

uint64_t Fibonacci(unsigned char n) {static uint64_t fib[256] = {0, 1};if(n == 0) return 0;if( fib[n] != 0 ) return fib[n];fib[n] = Fibonacci(n - 1) + Fibonacci(n - 2);return fib[n]; }

這個代碼還用到了 static 型局部數據變量的一個特性：沒有指定值的元素自動初始化為 0。如果沒有這個特性，我們的程序中就要寫上 255 個 0 了。

除了上面給出的兩種 O(n) 算法之外，還有沒有更快的計算 F(n) 的方法呢？ 答案是肯定的。
我們將遞推表達式變變型就能得到：

(F(1)F(2))=(0111)(F(0)F(1))
(F(2)F(3))=(0111)(F(1)F(2))=(0111)2(F(0)F(1))
(F(n?1)F(n))=(0111)n?1(F(0)F(1))

因此，計算 F(n) 就變成了計算一個矩陣的 n?1 次方的問題了。而這個問題是有快速算法的。
當 n 為偶數時，Mn=Mn/2×Mn/2 所以只要計算出了 Mn/2 了之后再自乘一下就行了。
當 n 為 奇數時，Mn=M(n?1)/2×M(n?1)/2+M 所以只要計算出了 M(n?1)/2 了之后自乘一下在加一下自己就可以了。

也就是說當 n=2m 時，只需要進行 m 次乘法計算就可以了。當 n<2m 時，最多也就是進行 m 次乘法計算 和 m 次加法計算。所以算法復雜度是 O(log(n))。當 n 較大時，log(n)?n，所以當 n 較大時這樣計算會快的多。這里就不寫出這種算法的具體實現了，感興趣的同學可以自己寫寫。

這里還有一個問題一直沒有解決，就是我們的程序可以正確計算到 n 為多少。 我們知道一個 m 位的無符號整數可以表示的最大的整數是 2m?1。當 F(n)>2m?1 自然計算結果就是錯誤的了。 估計這個最大的 n 還要用到我們上面給出的通項公式的近似結果：
F(n)≈5√51+5√2n≈0.4472×1.618n
簡單的計算可知：

0.4472≈2?1.1611.618≈20.6942

所以：

F(n)≈0.4472×1.618n≈20.6942n?1.161F(47)≈231.4664F(48)≈232.1606F(93)≈263.3996F(94)≈264.0938

所以 32 位無符號整數最大可以表示到 F(47)，64 位無符號整數最大可以表示到 F(93)。

總結

以上是生活随笔為你收集整理的Fibonacci 数列及其计算方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。