杭電 OJ 2011 題解：交替調和級數前 N 項求和的 C 語言高效實現

題目描述

輸入 m 個測試用例，每用例給定整數 x，計算交替調和級數前 x 項和：

S = 1 - 1/2 + 1/3 - 1/4 + ... + (-1)^(x+1) * 1/x

輸出保留兩位小數。所有輸入讀完後統一輸出。

算法分析

• 直接模擬：單層循環累加，符號翻轉。時間 O(x)，空間 O(1)。
• 數值穩定性：項數 ≤ 1000 (題目隱含)，float 精度足夠，double 更穩健。
• I/O 優化：先讀所有輸入存入數組，再批量輸出，避免交互開銷。

核心代碼 (標準 C，可直接 AC)

#include 

int main(void) {
    int m;
    scanf("%d", &m);
    float results[1000]; // 假設 m ≤ 1000
    
    for (int i = 0; i < m; i++) {
        int x;
        scanf("%d", &x);
        float sum = 0.0f;
        int sign = 1; // 1, -1, 1, -1 ...
        
        for (int j = 1; j <= x; j++) {
            sum += sign * 1.0f / j; // 1.0f 強制浮點除法
            sign = -sign;           // 符號翻轉
        }
        results[i] = sum;
    }
    
    for (int i = 0; i < m; i++) {
        printf("%.2f\n", results[i]);
    }
    return 0;
}

關鍵點解析

進階優化 (大 x 場景)

若 x 極大 (如 10⁷)，直接求和較慢，可利用數學公式：

// 交替調和級數和 = ln(2) + (-1)^(n+1) * ∫_0^1 t^n/(1+t) dt
// 偶數項：S_2n = H_2n - H_n (H 為調和數)
// 可預計算調和數前綴和，O(1) 答題

但本題數據範圍小，直接模擬最簡潔可靠。

常見錯誤與 AC 技巧

1. ❌ sum += 1/j → 整除歸零。✅ sum += 1.0/j 或 1.0f/j。
2. ❌ 符號邏輯反：if (j%2) sum += ... else sum -= ... 易寫錯邊界。✅ sign = -sign 統一。
3. ❌ 邊讀邊輸出 → 題目要求批量輸出。✅ 存數組後統一 printf。
4. ✅ 開啟 -O2 優化，循環自動向量化，速度極快。

總結

本題考察浮點除法陷阱、符號翻轉技巧、批量 I/O 邏輯。掌握 1.0/j 強制浮點化與 sign = -sign 翻轉模式，即可輕鬆 AC。代碼簡潔、邏輯清晰、零依賴，是入門級數值計算題的標準解法。