概念

斐波那契數列（Fibonacci sequence），又稱黃金分割數列，因數學家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波那契數列以如下被以遞推的方法定義：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
在C++中可以有多種方法求斐波那契數列

問題描述

菲波那契數列是指這樣的數列: 數列的第一個和第二個數都為1，接下來每個數都等于前面2個數之和。
給出一個正整數k，要求菲波那契數列中第k個數是多少。
題目鏈接：
OpenJudge NOI 1.5 17:菲波那契數列

1. 迭代法

• 設置變量n2，n1，表示當前已知的倒數第二項，和最后一項
• 求新的項t，t = n1 + n2;
• 新的倒數第二項是原來的最后一項，所以使n2 = n1;
• t將會是新的最后一項，有n1 = t;
• i為3時求出第3項，i為4時求出第4項，i為k時求出第k項。循環i從3循環到k，即可求出第k項

時間內復雜度：$O(n)$，空間復雜度：$O(1)$

#include<bits/stdc++.h> using namespace std; int main() {int k, n2 = 1, n1 = 1, t;//n2,n1是當前求出的倒數第二項，和最后一項 cin >> k;for(int i = 3; i <= k; ++i){t = n1 + n2;n2 = n1;n1 = t;}cout << n1;return 0; }

2. 遞推法

• 遞推狀態：a[i]為斐波那契數列第i項
• 遞推關系：斐波那契數列第i項為其前兩項之和，即a[i] = a[i-1]+a[i-2]
• 初始狀態：第1項與第2項值為1

時間內復雜度：$O(n)$，空間復雜度：$O(n)$

#include<bits/stdc++.h> using namespace std; int main() {int k, a[50];//a[i]為斐波那契數列第i項a[1] = a[2] = 1;cin >> k;for(int i = 3; i <= k; ++i)a[i] = a[i-1] + a[i-2];cout << a[k];return 0; }

3. 遞歸法（一般）

• 遞歸問題：求斐波那契數列第k項
• 遞歸關系：想要求第k項，必須先求第k-1項和第k-2項，而后將這兩項加和
• 遞歸出口：斐波那契數列第1和第2項為1

時間內復雜度：$O(2^n)$，空間復雜度：$O(n)$

#include<bits/stdc++.h> using namespace std; int fib(int k)//求斐波那契數列第k項 {if(k == 1 || k == 2)return 1;elsereturn fib(k - 1) + fib(k - 2); } int main() {int k;cin >> k;cout << fib(k);return 0; }

同一種思路，用棧將遞歸轉為非遞歸寫法

#include<bits/stdc++.h> using namespace std; int main() {stack<int> stk; int n, r = 0, m;cin >> n;stk.push(n);while(stk.empty() == false){m = stk.top();//出棧stk.pop();if(m == 2 || m == 1)//如果遇到第二項或第一項，直接把值加到結果res中r += 1;else{//把后兩項入棧stk.push(m-1);stk.push(m-2);}}cout << r;return 0; }

用以上兩段代碼提交【OpenJudge NOI 1.5 17:菲波那契數列】會超時。該算法時間復雜度過高了，輸入40時，基本要1秒后才能得到結果。

4. 記憶化遞歸法

在遞歸算法的基礎上增加記憶狀態：a[i]表示斐波那契數列的第i項
在遞歸時，如果要求斐波那契數列第i項，先看這一項是否已經求出來過。如果已經求出過，那么直接取值。在求出一項后，將其存入記憶狀態數組中。
時間內復雜度：$O(n)$，空間復雜度：$O(n)$

#include<bits/stdc++.h> using namespace std; int a[50];//a[i]:斐波那契數列第i項 int fib(int k)//求斐波那契數列第k項 {if(a[k] > 0)return a[k];elsereturn a[k] = fib(k-1) + fib(k-2); } int main() {int k;cin >> k;a[1] = a[2] = 1;cout << fib(k);return 0; }

5. 尾遞歸法

當遞歸調用是整個函數體中最后執行的語句且它的返回值不屬于表達式的一部分時，這個遞歸調用就是尾遞歸。
尾遞歸調用結束，上一次調用也就結束了，所以沒有必要存儲上一次調用中用到的臨時變量。現代編譯器都會針對這一特性對尾遞歸進行優化，減少算法的空間復雜度。
用g++編譯時，加上-O2選項，即可開啟尾遞歸優化。
時間內復雜度：$O(n)$，空間復雜度：$O(1)$

#include<bits/stdc++.h> using namespace std; int fib(int n1, int n2, int k)//倒數第1項是n1，倒數第2項是n2，計算k-1次 {if(k == 1)return n2;elsereturn fib(n1+n2, n1, k-1); } int main() {int k;cin >> k;cout << fib(1, 1, k);return 0; }

6. 公式法

已知求斐波那契數列的通項公式$F_n=\frac{(\frac{1+\sqrt{5}}{2}{)}^n?(\frac{1?\sqrt{5}}{2}{)}^n}{\sqrt{5}}$
輸入n，代入公式，即可求值
時間內復雜度：$O(1)$，空間復雜度：$O(1)$

#include<bits/stdc++.h> using namespace std; int main() {int n;cin >> n;cout << int((pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n))/sqrt(5));return 0; }

總結

以上是生活随笔為你收集整理的【君义精讲】多种方法求斐波那契数列的全部內容，希望文章能夠幫你解決所遇到的問題。

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