數列求和：解析遞增數列前n項和的計算方法與C語言實現

問題描述

給定一個數列：1, 2, 4, 7, 11, 16, 22……，請計算該數列前 n 項的和。輸入包含多組測試數據，每組一個整數 n (0 < n < 1000)，輸出對應的前 n 項和。

數列規律分析

觀察數列可以發現：

• 第 1 項：a₁ = 1
• 第 2 項：a₂ = a₁ + 1 = 2
• 第 3 項：a₃ = a₂ + 2 = 4
• 第 4 項：a₄ = a₃ + 3 = 7
• 第 k 項：aₖ = aₖ₋₁ + (k-1)

這是一個二階等差數列，通項公式可推導為：aₖ = 1 + k(k-1)/2

解題思路

採用動態生成數列的方法：

1. 初始化陣列 array[0] = 1
2. 利用遞推關係 array[i] = array[i-1] + i 生成前 n 項
3. 累加陣列前 n 個元素得到總和
4. 處理多組輸入直到 EOF

代碼實現

#include <stdio.h>

int main() {
    int i, num, sum;
    int array[1001];

    while (scanf("%d", &num) != EOF && (num > 0 && num < 1000)) {
        sum = 0;
        array[0] = 1;
        for (i = 1; i < num; i++) {
            array[i] = array[i-1] + i;
        }

        for (i = 0; i < num; i++) {
            sum += array[i];
        }
        printf("%d\n", sum);
    }
    return 0;
}

複雜度分析

時間複雜度：O(n) 每組測試數據
空間複雜度：O(n) 需要存儲數列陣列

測試樣例

輸入：

3
4

輸出：

7
14

驗證：n=3 時數列為 1,2,4 和為 7；n=4 時數列為 1,2,4,7 和為 14。