d283 - 大數加法
題目描述
題目要求計算費氏數列的第 n 項，其中 n 的範圍是 0 到 20000。由於費氏數列的增長速度很快，直接使用整數類型會導致溢位，因此需要使用大數運算來處理。
解題思路
本題使用動態規劃的思想，預先計算出從 F0 到 F20000 的所有費氏數列項，並將它們儲存在字串陣列 f 中。每次計算新的費氏數列項時，使用一個 add 函數來執行大數加法。add 函數將兩個字串表示的大數轉換為整數陣列，然後逐位進行加法運算，處理進位，最後將結果轉換回字串。主程式讀取輸入的 n，然後輸出 f[n] 的值。
複雜度分析
- 時間複雜度: O(N * M)，其中 N 是費氏數列項的數量 (20000)，M 是大數的平均長度 (約 6000)。因為需要計算 20000 個費氏數列項，並且每次計算都需要執行大數加法，大數加法的時間複雜度與大數的長度成正比。
- 空間複雜度: O(M)，其中 M 是大數的平均長度 (約 6000)。因為需要儲存 20001 個字串，每個字串的長度約為 6000。
程式碼
#include <iostream>
using namespace std;
string f[20001]={"0","1"};
inline string add(string a,string b){
int aa[6001]={0},bb[6001]={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<=20000;++i)
f[i]=add(f[i-1],f[i-2]);
int n;
while(cin >> n)
cout << f[n] << "\n";
}