ZeroJudge 解題筆記：e470. 無窮級數之和(一)

作者：王一哲
日期：2025年9月24日


ZeroJudge 題目連結：e470. 無窮級數之和(一)

解題想法

這題考數學，當 $n$ 很大時，有近似公式 $$ \sum_{i=1}^{n} \frac{1}{i} = \ln n + \gamma + \frac{1}{2n} $$ 其中 $\gamma = 5772156649$。

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys, math

def harmonic_number(n):
    if n <= 20:  # 如果 n 小於等於 20，直接用迴圈計算
        isum = 0
        for i in range(1, n+1): isum += 1/i
        return isum
    gamma = 0.5772156649  # 反之，代近似公式
    return math.log(n) + gamma + 1.0 / (2 * n)

for line in sys.stdin:
    print(f"{harmonic_number(int(line)):.3f}")

C++ 程式碼

使用時間約為 2 ms，記憶體約為 148 kB，通過測試。

#include <cstdio>
#include <cmath>
using namespace std;

float harmonic_number(int n) {
    if (n <= 20) {  // 如果 n 小於等於 20，直接用迴圈計算
        float isum = 0.0;
        for(int i=1; i<=n; i++) isum += 1.0/i;
        return isum;
    }
    return log(n) + 0.5772156649 + 1.0 / (2 * n);  // 反之，代近似公式
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF) printf("%.3f\n", harmonic_number(n));
    return 0;
}