原文轉載自林健隨筆的“淺議Fibonacci（斐波納契）數列求解”

Fibonacci 數列

描述了動物繁殖數量、植物花序變化等自然規律。作為一個經典的數學問題，Fibonacci數列常作為例子出現在程序設計、數據結構與算法等多個相關學科中。

下面簡單地分析一下常見的Fibonacci數列求解算法。

遞歸法

大多數教材在講解遞歸算法時總喜歡以Fibonacci數列為例，這是因為我們可以直觀地從定義公式的第三行看出Fibonacci數列的遞歸性。其C++實現如下：

unsigned long Fib(int n) {if (n <= 1) {return n;} else {return Fib(n - 1) + Fib(n - 2);} }

遞歸算法與定義公式十分吻合，容易理解，但計算過程存在大量重復的運算，時間復雜度達到了O(2^n)，使用的內存空間也隨著函數調用棧的增長而增長。這顯然不適于實用的程序。

表驅動的遞歸法

(編者注：動態規劃)
這里不提純粹的表驅動法，因為對于項數未知的Fibonacci數列開啟大片的空間來換取時間未免不值得且不負責。我們只是為了消除遞歸法中大量重復的運算，可以將已經計算過的中間值存入一個表，已備后續使用：

#define MAX_LOG 20 static unsigned long Logs[MAX_LOG] = {0}; unsigned long Fib(int n) {if (n <= 1) {return n;} else if (n < MAX_LOG && Logs[n] != 0) {return Logs[n];} else {Logs[n] = Fib(n - 1) + Fib(n - 2);return Logs[n];} }

當n小于保存的表長時，由于每個中間值只計算一次，時間復雜度降為O(n)。但隨著n的增大，要想維持O(n)的時間復雜度，就必須擴大保存的表長，這就造成了存儲空間的浪費。

迭代法

(編者注：遞推)
求Fibonacci數列第n項時雖然要用到前面兩項的值，但它們僅作為臨時計算的中間值，不作為結果輸出，因此無保留的必要，完全可以轉化成迭代法求解：

unsigned long Fib(int n) {int i;unsigned long a = 0, b = 1, c;if (n <= 1) {return n;} else {for (i = 2; i <= n; i++) {c = a + b;a = b;b = c;}return c;} }

迭代法的時間復雜度為O(n)，使用的內存空間也不會動態上漲。個人認為Fibonacci數列更適宜作為迭代法而非遞歸法的典例出現在教材上。

下面給出兩種數學性較強的算法。考慮到表達的簡潔性，用Matlab實現

轉移矩陣法

此方法通常見于線性代數中的Markov過程示例。Fibonacci數列第n項與第n-1項可以通過轉移矩陣的n-1次迭代求出：

function y = Fib(n)first = [1; 0];trans = [1 1; 1 0];last = trans ^ (n - 1) * first;y = last(1, 1); end

此算法的時間復雜度相當于計算矩陣乘方的時間復雜度。在計算2階矩陣n次方時，如果直接按矩陣乘法定義式展開，不加特別優化，其時間復雜度為O(n)。

通項公式法

Fibonacci數列的通項公式如下（證明略）：

function y = Fib(n)sr5 = sqrt(5);y = uint32((((1 + sr5) / 2) ^ n - ((1 - sr5) / 2) ^ n) / sr5); end

該方法的時間復雜度貌似為O(1)，但我們還應該考慮乘方運算的時間消耗。不加特別優化時，用乘法實現n次乘方的時間復雜度為O(n)。考慮到浮點數計算效率和精度問題，此方法在計算機實現時不如轉移矩陣法。

下面再給出兩種對計算機實現有特別意義，但同時有一定局限性的實現方法（只是實現方法，不能稱為新的算法）。其中使用了一些C++編程技巧，對使用其它語言實現也有一定的參考價值：

模板元編程法

通常我們在C++中使用模板，僅限于類模板與函數模板。事實上C++支持模板元編程，理論上可以在編譯時執行任何計算（甚至包含選擇、循環、遞歸等結構）。代碼如下：

#define Fib(N) FibT<N>::Val template<int n> struct FibT {enum{Val = FibT<n - 1>::Val + FibT<n - 2>::Val}; }; template<> struct FibT<0> {enum{Val = 0}; }; template<> struct FibT<1> {enum{Val = 1}; };

我們用一個結構體作為模板的載體，用一個枚舉值保存運算結果。其中第一個模板為基本遞歸過程（使用遞歸算法是為了說明的簡便，完全可以用其它算法替代，以加速編譯過程），后兩個模板為n=0、1時的模板特化。通過#define語句將模板調用簡寫成類似函數調用的方式。程序在編譯時運算所需的 Fibonacci數列項，將結果作為常量嵌入編譯好的程序。運行時直接使用結果，時間復雜度真正地變成了O(1)。但這一方法最大的局限就是只能對常量嵌入，程序中出現諸如計算Fib(i++)的情況則無能為力。盡管如此，這比在代碼中手工計算并寫入所需的值要直觀準確，比通過純粹的表驅動法“空間換時間”要方便快捷

函數對象法

此方法主要用于C++ STL編程的通用算法方面，其執行行為也有別于以上其它方法：

class Fib { public:Fib() : a(0), b(1), n(0){}unsigned long operator()(){if (n <= 1) {n++;return n - 1;} else {int c;c = a + b;a = b;b = c;return c;}} private:int a, b, n; };

這個函數類對象的行為可以理解為一個“Fibonacci數列發生器”，其測試性調用如下，程序將依次打印

void test(int i) {Fib fib;do {cout << fib() << endl;} while (i--); }

函數對象具有與函數指針類似的行為，同時又能保存自身的一些屬性，因此常用于STL通用算法編程。但針對單個的Fibonacci數列項求值，靈活性不如一般的方法。
希望讀者能夠從上面的算法分析中舉一反三，有所領悟。

參考資料

Bruce Eckel，Thinking In C++ Volume 2: Practical Programming，機械工業出版社，2006

William J. Collins，Data Structures and the Standard Template Library，機械工業出版社，2003

Knott's Surrey University，The Home page for Fibonacci Numbers and the Golden Section，http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/

總結

以上是生活随笔為你收集整理的[CS101] 转载：浅议Fibonacci（斐波纳契）数列求解的全部內容，希望文章能夠幫你解決所遇到的問題。

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