d356 - NOIP2002 1.级数求和

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算最小的 n，使得調和級數 Sn = 1 + 1/2 + 1/3 + ... + 1/n 大於給定的整數 K (1 <= K <= 15)。

解題思路

此題可以使用貪心策略，逐項累加調和級數，直到和超過 K。由於 K 的範圍較小，且調和級數增長緩慢，因此可以通過簡單的迴圈迭代來實現。每次迭代中，將 1/b 加到 sum 上，並將 b 增加 1，同時將 ans 增加 1。當 sum 大於 K 時，ans 即為所求的最小 n。

複雜度分析

• 時間複雜度: O(n)，其中 n 是滿足 Sn > K 的最小整數。由於 K 的範圍是 1 到 15，n 的最大值不會太大，因此時間複雜度可以視為常數級別。
• 空間複雜度: O(1)，程式碼只使用了幾個變數來存儲中間結果，空間複雜度為常數級別。

程式碼

#include <iostream>
using namespace std;
int main(){
	double a,b;
	while(cin >> a){
		double sum=0,ans=0;
		b=1;
		while(sum<=a){
			sum+=1/b;
			b++;
			ans++;
		}
		cout << ans << endl;
	}
}