杭電 OJ 多項式求和問題：交替調和級數前 N 項和的 C 語言高精度解法

問題描述：交替調和級數部分和

計算級數 S(n) = 1 - 1/2 + 1/3 - 1/4 + ... + (-1)^(n+1)/n 的前 n 項和，輸出保留兩位小數。輸入包含多組測試數據，m < 100 組，每組一個 n < 1000。

一、 數學本質與算法選擇

• 此級數為交替調和級數，收斂於 ln(2) ≈ 0.693147。
• n ≤ 1000 規模極小，直接循環累加 即可，時間複雜度 O(n) 完全足夠。
• 需注意浮點精度：使用 double 而非 float，避免累積誤差影響第 2 位小數。
• 符號翻轉：(-1)^(k+1) 可用 (k%2==1)?1:-1 或維護 sign = -sign 變量，避免調用 pow() 產生額外開銷與精度損失。

二、 標準解法代碼

#include 

int main() {
    int m, n;
    scanf("%d", &m);           // 讀取測試組數
    while (m--) {
        scanf("%d", &n);
        double sum = 0.0;
        int sign = 1;          // 首項為正
        for (int i = 1; i <= n; i++) {
            sum += sign * (1.0 / i); // 關鍵：1.0 強制雙精度除法
            sign = -sign;      // 符號翻轉
        }
        printf("%.2f\n", sum); // 保留兩位小數（四捨五入）
    }
    return 0;
}

三、 關鍵點深度解析

1. 避免 pow(-1, k) 的陷阱

// 原始碼錯誤示範
for (i = 1; i <= n; i++) {
    int j = pow(-1, i+1);  // pow 返回 double，隱式轉 int 可能產生 0.9999→0 錯誤
    sum += j * (1.0/i);
}

// 正確整數符號翻轉
int sign = 1;
for (int i = 1; i <= n; i++) {
    sum += sign / (double)i;
    sign = -sign;
}

2. 1.0/i` vs 1/i`

1 / i      // 整數除法！i>1 時結果恆為 0
1.0 / i    // 雙精度除法，正確得到小數
(double)1 / i // 等價寫法

3. 輸出格式控制

printf("%.2f\n", sum); // %.2f 自動四捨五入保留兩位小數
// 注意：原始碼 printf("%.2\n", sum) 缺少 'f' 會導致未定義行為

4. 讀取輸入格式

題目說「第二行包含 m 個整數」，但樣例輸入為：

2
1 2

實際可能換行也可能不換行，scanf("%d", &n) 自動跳過空白字符（含換行），while(m--) 循環讀取 m 次即可，無需關心行結構。

四、 進階優化：預計算前綴和

若測試組數極大（如 10^5）且 n 重複查詢，可預計算 prefix[1000]：

double prefix[1001] = {0};
int sign = 1;
for (int i = 1; i <= 1000; i++) {
    prefix[i] = prefix[i-1] + sign / (double)i;
    sign = -sign;
}
// 查詢時 O(1)
while (m--) {
    scanf("%d", &n);
    printf("%.2f\n", prefix[n]);
}

五、 常見錯誤總結

總結：此題核心考察浮點累加精度、整數除法陷阱、符號翻轉技巧、輸出格式控制。掌握 double 累加、1.0/i 強制浮點除法、sign=-sign 避免 pow、%.2f 格式化，即可輕松 AC。預計算前綴和思想可擴展至大規模同類查詢問題。