山東理工大學ACM 1238：求數列的和 - C語言解題詳解

題目描述

給定一個數列，其第一項為 n，其後每一項均為前一項的平方根。要求計算該數列前 m 項的和。

輸入格式

輸入包含多組測試數據，每組佔一行，由兩個整數 n（n < 10000）和 m（m < 1000）組成。

輸出格式

對於每組輸入數據，輸出該數列的和，每個測試實例佔一行，結果保留兩位小數。

範例

輸入範例

81 4
2 2

輸出範例

94.73
3.41

解題思路

這是一道典型的模擬題。由於 m 最大僅 1000，直接模擬計算完全可行。算法步驟如下：

1. 讀取 n 和 m，直到 EOF。
2. 初始化總和 sum = n，當前項 current = n。
3. 循環 m-1 次：每次將 current 更新為其平方根 sqrt(current)，並累加到 sum。
4. 輸出 sum，格式化為保留兩位小數。

參考代碼 (C語言)

#include <stdio.h>
#include <math.h>

int main() {
    int n, m;
    double sum, current;

    while (scanf("%d %d", &n, &m) != EOF) {
        sum = n;
        current = n;
        for (int i = 1; i < m; i++) {
            current = sqrt(current);
            sum += current;
        }
        printf("%.2f\n", sum);
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(m) 每組測試數據，最壞情況約 1000 次運算，極快。
• 空間複雜度：O(1)，僅使用常數額外空間。

注意事項

• 需包含 math.h 並鏈接數學庫（編譯時加 -lm）。
• 輸出格式必須嚴格保留兩位小數，使用 %.2f 或 %.2lf。
• 輸入以 EOF 結束，使用 while(scanf(...) != EOF) 即可處理多組數據。