如題：

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0）。

這道題基本上學過算法的人都直到，斐波那契數列即，即1，1，2，3，5.......

用數學公式描述即 f(n) = f(n-1) + f(n-2)，很多教科書上都提供了遞歸算法，雖然，能夠滿足，但是效率是在太低了，存在大量重復計算，比如，計算f(5)的時候，需要計算f(4)和f(3)，計算f(6)的時候，需要計算f(4)和f(5)，顯然，f(4)和f(5)重復計算了，隨著n的增大，重復計算量越來越多。

為了減少重復計算量，此題最好的方式是使用循環法，不僅僅是此題，平常運用遞歸求解問題的時候，也要注意是否存在重復計算，如果存在的話，則需使用循環法求解。再循環體中保存前一步得到的值即可。思想上有點類似dp動態規劃。

此題變種有很多，例如，青蛙跳臺階，仔細分析，本質上也是求斐波那契數列問題。

本題的c++解法如下：

//f(n) = f(n-1) + f(n-2); class Solution { public:int Fibonacci(int n) {int i = 3, v1 = 1, v2 = 1, val;//特殊情況處理if (n < 1)return 0;if (n < 3)return 1;//循環求解，保存上一步得到的值while (i <= n){val = v1 + v2;v1 = v2;v2 = val;i++;}return val;} };

=============================================================================================

Linux應用程序、內核、驅動、后臺開發交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結

以上是生活随笔為你收集整理的《剑指offer》c++版本 10. 斐波那契数列的全部內容，希望文章能夠幫你解決所遇到的問題。

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