e470 - 無窮級數之和(一)

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算調和級數的和，即 1/1 + 1/2 + 1/3 + ... + 1/n，並將結果四捨五入到小數點以下第三位。由於直接計算 O(n) 的時間複雜度不符合題目提示，因此需要使用近似公式。

解題思路

題目提示有公式可用，調和級數存在近似公式： H(n) ≈ ln(n) + γ + 1/(2n) - 1/(12n^2) 其中，ln(n) 是 n 的自然對數，γ 是歐拉-馬斯刻若尼常數 (約為 0.5772156649)。 程式碼直接使用了這個公式來計算調和級數的近似值，並使用 fixed 和 setprecision(3) 來控制輸出精度。

複雜度分析

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

程式碼

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
double n,y=0.577215664901532;
int main(){
	while(cin >> n){
		cout << fixed << setprecision(3) << log(n) + y + (1/(2*n) - (1/(12*n*n))) << "\n";
	}
}