斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，因數(shù)學家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學上，斐波那契數(shù)列以如下被以遞推的方法定義：F(0)=1，F(xiàn)(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
在C++中可以有多種方法求斐波那契數(shù)列
菲波那契數(shù)列是指這樣的數(shù)列: 數(shù)列的第一個和第二個數(shù)都為1，接下來每個數(shù)都等于前面2個數(shù)之和。
給出一個正整數(shù)k，要求菲波那契數(shù)列中第k個數(shù)是多少。
題目鏈接：
OpenJudge NOI 1.5 17:菲波那契數(shù)列
重慶分公司
重慶分公司
t = n1 + n2;n2 = n1;n1 = t;時間內復雜度： O ( n ) O(n) O(n)，空間復雜度： O ( 1 ) O(1) O(1)
#includeusing namespace std;
int main()
{int k, n2 = 1, n1 = 1, t;//n2,n1是當前求出的倒數(shù)第二項，和最后一項
cin >>k;
for(int i = 3; i<= k; ++i)
{t = n1 + n2;
n2 = n1;
n1 = t;
}
cout<< n1;
return 0;
} a[i]為斐波那契數(shù)列第i項a[i] = a[i-1]+a[i-2]時間內復雜度： O ( n ) O(n) O(n)，空間復雜度： O ( n ) O(n) O(n)
#includeusing namespace std;
int main()
{int k, a[50];//a[i]為斐波那契數(shù)列第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;
} 時間內復雜度： O ( 2 n ) O(2^n) O(2n)，空間復雜度： O ( n ) O(n) O(n)
#includeusing namespace std;
int fib(int k)//求斐波那契數(shù)列第k項
{if(k == 1 || k == 2)
return 1;
else
return fib(k - 1) + fib(k - 2);
}
int main()
{int k;
cin >>k;
cout<< fib(k);
return 0;
} 同一種思路，用棧將遞歸轉為非遞歸寫法
#includeusing namespace std;
int main()
{stackstk;
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:菲波那契數(shù)列】會超時。該算法時間復雜度過高了，輸入40時，基本要1秒后才能得到結果。
4. 記憶化遞歸法在遞歸算法的基礎上增加記憶狀態(tài)：a[i]表示斐波那契數(shù)列的第i項
在遞歸時，如果要求斐波那契數(shù)列第i項，先看這一項是否已經(jīng)求出來過。如果已經(jīng)求出過，那么直接取值。在求出一項后，將其存入記憶狀態(tài)數(shù)組中。
時間內復雜度：
O
(
n
)
O(n)
O(n)，空間復雜度：
O
(
n
)
O(n)
O(n)
#includeusing namespace std;
int a[50];//a[i]:斐波那契數(shù)列第i項
int fib(int k)//求斐波那契數(shù)列第k項
{if(a[k] >0)
return a[k];
else
return a[k] = fib(k-1) + fib(k-2);
}
int main()
{int k;
cin >>k;
a[1] = a[2] = 1;
cout<< fib(k);
return 0;
} 當遞歸調用是整個函數(shù)體中最后執(zhí)行的語句且它的返回值不屬于表達式的一部分時，這個遞歸調用就是尾遞歸。
尾遞歸調用結束，上一次調用也就結束了，所以沒有必要存儲上一次調用中用到的臨時變量?，F(xiàn)代編譯器都會針對這一特性對尾遞歸進行優(yōu)化，減少算法的空間復雜度。
用g++編譯時，加上-O2選項，即可開啟尾遞歸優(yōu)化。
時間內復雜度：
O
(
n
)
O(n)
O(n)，空間復雜度：
O
(
1
)
O(1)
O(1)
#includeusing namespace std;
int fib(int n1, int n2, int k)//倒數(shù)第1項是n1，倒數(shù)第2項是n2，計算k-1次
{if(k == 1)
return n2;
else
return fib(n1+n2, n1, k-1);
}
int main()
{int k;
cin >>k;
cout<< fib(1, 1, k);
return 0;
} 已知求斐波那契數(shù)列的通項公式
F
n
=
(
1
+
5
2
)
n
?
(
1
?
5
2
)
n
5
F_n = \frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}
Fn?=5
?(21+5
??)n?(21?5
??)n?
輸入n，代入公式，即可求值
時間內復雜度：
O
(
1
)
O(1)
O(1)，空間復雜度：
O
(
1
)
O(1)
O(1)
#includeusing 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;
} 你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
