f424 - 高雄市109年資訊競賽國中組第二題
題目描述
題目要求計算費波那契數列的第 n 項，其中 n 是輸入的整數。費波那契數列定義如下：F(1) = 1, F(2) = 3, F(i) = F(i-1) + F(i-2) (i > 2)。
解題思路
這題是典型的費波那契數列問題。由於 n 的範圍不大 (n <= 43)，可以使用動態規劃的方式預先計算出所有需要的費波那契數，然後直接輸出第 n 項的值。程式碼中，ans 陣列儲存了費波那契數列的值，從 ans[0] 到 ans[43]。迴圈計算出數列的每一項，然後根據輸入的 n 值輸出 ans[n-1]。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int ans[44]={1,3},n;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
for(int i=2;i<44;++i)
ans[i]=ans[i-1]+ans[i-2];
n=read();
write(ans[n-1]);
}