b127 - 會議中心（Room）

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算第 n 次擴充時正方形會議室的邊長。擴充規則是每次擴充都形成一個更大的正方形，且邊長與前一次擴充的邊長相關。題目給定的輸入 n 代表擴充的次數。

解題思路

觀察題目描述和範例，可以發現每次擴充的邊長實際上是費氏數列。第一次擴充邊長為 1，第二次擴充邊長為 1，第三次擴充邊長為 2，第四次擴充邊長為 3，第五次擴充邊長為 5，以此類推。因此，第 n 次擴充的邊長就是第 n 個費氏數。程式碼使用迴圈計算費氏數列，直到第 n 個數，並輸出該數。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int main(){
	int n;
	while(cin >> n){
		int i=1,ans=0,j=1;
		for(;n>0;n--){
			ans+=j;
			j=i;
			i=ans;
		}
		cout << ans << endl;
	}
}