ACM 1007 Numerical Summation of a Series 解題報告

ZOJ 1007 Numerical Summation of a Series 題解

本題要求計算函數 psi(x) 在 x ∈ [0, 2] 區間、步長 0.001 的值並格式化輸出。屬於基礎數值計算與輸出格式控制練習題。

題目數學模型

對每個 x，計算：

psi(x) = (1-x) * Σ[k=1 to 9999] 1 / (k*(k+1)*(k+x)) + (1-x)/(2*10000^2) + 1

輸出格式：%5.3f %16.12f，即 x 佔 5 位小數點後 3 位，psi(x) 佔 16 位小數點後 12 位。

關鍵實現細節

1. 迴圈邊界：x 從 0 到 2.000，步長 0.001，共 2001 個點。使用 for (x = 0; x <= 2.000; x += 0.001) 需注意浮點誤差累積，實際建議用整數迴圈 for (int i = 0; i <= 2000; i++) { x = i * 0.001; }
2. 求和上限：題目給定 k < 10000，即 k = 1..9999
3. 精度要求：雙精度 double 足夠，最終項 (1-x)/(2*10000^2) 為尾項修正
4. 輸出格式：嚴格遵循 %5.3f %16.12f，包含空格對齊

標準 AC 代碼

#include 

int main() {
    int k;
    double x, psi_x;
    for (int i = 0; i <= 2000; i++) {
        x = i * 0.001;
        psi_x = 0.0;
        for (k = 1; k < 10000; k++) {
            psi_x += 1.0 / (k * (k + 1) * (k + x));
        }
        psi_x = psi_x * (1 - x) + (1 - x) / (2.0 * 10000 * 10000) + 1.0;
        printf("%5.3f %16.12f\n", x, psi_x);
    }
    return 0;
}

優化提示

• 內層迴圈可提取不變量，但 9999 次迴圈在現代 CPU 上極快，無需優化
• 若要求更高性能，可預計算 1.0/(k*(k+1)) 存入陣列，內層僅做一次除法
• 注意 k*(k+1)*(k+x) 可能溢出 int，需強制轉 double 計算

常見錯誤

1. 使用 float 導致精度不足
2. x 迴圈條件 x <= 2.0 浮點誤差導致少輸出或多輸出一行
3. 輸出格式不符 (寬度、小數位、空格)
4. 求和上限寫成 k <= 10000 多加一項