k402 - 費氏數列

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算費氏數列的第 n 項。費氏數列的定義是 F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n >= 2)。

解題思路

此題採用迭代的方式計算費氏數列。初始化前兩個數 a 和 b 為 0 和 1。然後，迴圈 n 次，每次計算下一個數 c 為 a 和 b 的和，並更新 a 和 b 的值，使其分別為 b 和 c。迴圈結束後，c 即為費氏數列的第 n 項。由於題目輸入的 n 從 1 開始，因此需要特別處理 i=1 的情況，將 a 設為 1。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
long long n,a,b,c;
int main(){
	cin >> n;
	for(int i=0;i<n;++i){
		if(i==1)a=1;
		c=a+b;
		a=b;
		b=c;
	}
	cout << c;
}