a519 - 12459 - Bees' ancestors

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算蜜蜂 Willy 在特定世代的祖先數量。由於雄蜂只有一個母親，且每一代的祖先數量遵循費氏數列的規律，因此需要計算第 n 代的費氏數列值。

解題思路

這題的核心在於觀察祖先數量與世代之間的關係。第一代有 1 個祖先（母親），第二代有 2 個祖先（祖父母），第三代有 3 個祖先（曾祖父母）。可以發現，祖先的數量實際上是費氏數列。程式預先計算到第 80 代的費氏數列值，然後根據輸入的世代數，直接輸出對應的費氏數列值。

複雜度分析

• 時間複雜度: O(n + m)，其中 n 是預計算費氏數列的世代數 (80)，m 是輸入的世代數。預計算費氏數列需要 O(n) 時間，處理每個輸入需要 O(1) 時間。
• 空間複雜度: O(n)，用於儲存預計算的費氏數列。

程式碼

#include <iostream>
using namespace std;
int main(){
	long long int a[82]={1,2},b;
	for(int i=1;i<=80;i++){
		a[i+1]=a[i]+a[i-1];
	}
	while(cin >> b){
		if(b>0)
		cout << a[b-1]  << "\n";
	}
}