a216 - 數數愛明明

🔗 前往 ZeroJudge 原題

題目描述

題目描述了兩個遞迴關係：f(n) = n + f(n-1) 和 g(n) = f(n) + g(n-1)，其中 f(1) = g(1) = 1。要求計算給定 n 時 f(n) 和 g(n) 的值。

解題思路

題目要求計算兩個遞迴數列的值。由於 n 的範圍不大 (n <= 30000)，可以直接使用迴圈迭代的方式計算 f(n) 和 g(n)。初始化 f(1) 和 g(1) 為 1，然後從 day = 2 開始迭代到 n，每次更新 f(day) 和 g(day) 的值。

複雜度分析

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

程式碼

#include <iostream>

using namespace std;

int main (){
	
	long long int n,f,g=0;//f(n) = n + f(n-1);g(n) = f(n) + g(n-1) 
	while(cin >> n){
		long long int day=1;
		f=g=1;
		while(day<n){
			day++;
			f=day+f;
			g=f+g;
		}
		cout << f << " " << g << endl;
	}
	
	
}