c121 - 00495 - Fibonacci Freeze
題目描述
題目要求計算給定 n 的第 n 個費氏數列數字，其中 0 <= n <= 5000。由於費氏數列增長迅速，需要處理大數的情況。
解題思路
由於費氏數列的定義是遞迴的，但直接遞迴會導致重複計算，效率低下。因此，使用動態規劃的方法來解決這個問題。具體來說，我們建立一個陣列 f，其中 f[i] 儲存第 i 個費氏數列數字。然後，從 f[2] 開始，使用 f[i] = f[i-1] + f[i-2] 的公式計算每個費氏數列數字。由於需要處理大數，我們使用字串來儲存費氏數列數字，並實現一個字串加法函數。
複雜度分析
- 時間複雜度: O(N * M)，其中 N 是計算的費氏數列項數 (5000)，M 是最大費氏數列數字的位數。
- 空間複雜度: O(N)，用於儲存費氏數列數字的陣列。
程式碼
#include <iostream>
using namespace std;
string f[5001]={"0","1"};
inline string add(string a,string b){
int aa[2000]={0},bb[2000]={0},al=a.length(),bl=b.length();
string ans;
for(int i=0;i<al;++i)
aa[i]=a[al-i-1]-48;
for(int i=0;i<bl;++i)
bb[i]=b[bl-i-1]-48;
for(int i=0;i<=al;++i){
aa[i]+=bb[i];
if(aa[i]>9){
aa[i]-=10;
++aa[i+1];
}
}
if(aa[al]==0)
--al;
for(int i=al;i>=0;--i)
ans+=aa[i]+48;
return ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=2;i<=5000;++i)
f[i]=add(f[i-1],f[i-2]);
int n;
while(cin >> n){
cout << "The Fibonacci number for " << n<< " is " <<f[n] << "\n";
}
}