d261 - 11000 - Bee

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一種特殊的蜜蜂繁殖方式，要求計算在 N 年後公蜂和所有蜜蜂的數量。母蜂永生且每年生一隻公蜂，公蜂生一隻公蜂和一隻母蜂後死亡。

解題思路

這道題可以看作是一個變形的費氏數列問題。設 b[n] 表示第 n 年的公蜂數量，c[n] 表示第 n 年的母蜂數量，total[n] 表示第 n 年所有蜜蜂的數量。

• 第 0 年：b[0] = 0, c[0] = 1, total[0] = 1
• 第 n 年：
  • 母蜂每年生一隻公蜂，所以公蜂數量增加 1。
  • 第 n-1 年的公蜂生一隻公蜂和一隻母蜂，所以公蜂數量增加 b[n-1]，母蜂數量增加 b[n-1]。
  • 因此，b[n] = b[n-1] + 1，c[n] = c[n-1] + b[n-1]，total[n] = b[n] + c[n]。 程式碼中，b 儲存的是 b[n-1]，c 儲存的是 c[n-1]，c2 儲存的是 total[n-1]。迴圈計算 b[n] 和 c[n]，最後輸出 b[n] 和 total[n]。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int main(){
	int a;
	while(cin >> a){
		if(a<0)break;
		long long int b=0,c=1,c2=1;
		while(a--){
			c=b+c2+1;
			b=c2;
			c2=c;
		}
		cout << b << " " << c << "\n";
	} 
}