演算法題解：數列求和 — 找規律、推公式、O(1) 計算前 N 項和

題目描述

數列：1, 2, 4, 7, 11, 16, 22, ...

求前 n 項和 (0 < n < 1000)，多組測資直到 EOF。

規律分析

觀察相鄰項差值：

a₁ = 1
a₂ - a₁ = 1
a₃ - a₂ = 2
a₄ - a₃ = 3
a₅ - a₄ = 4
...
aₙ - aₙ₋₁ = n-1

∴ 通項公式：

aₙ = 1 + Σ(i=1 to n-1) i = 1 + (n-1)n/2 = (n² - n + 2)/2

前 N 項和公式推導

Sₙ = Σ(k=1 to n) aₖ = Σ (k² - k + 2)/2

= ½ [ Σk² - Σk + Σ2 ]

= ½ [ n(n+1)(2n+1)/6 - n(n+1)/2 + 2n ]

= n(n² + 5)/6

驗證

• n=3: 3×(9+5)/6 = 3×14/6 = 7 ✓ (1+2+4)
• n=4: 4×(16+5)/6 = 4×21/6 = 14 ✓ (1+2+4+7)

O(1) 直接計算程式碼

#include <stdio.h>

int main() {
    long long n;
    while (scanf("%lld", &n) == 1) {
        if (n <= 0 || n >= 1000) continue;
        long long sum = n * (n * n + 5) / 6;
        printf("%lld\n", sum);
    }
    return 0;
}

原始遞迴生成法 (教學參考)

// 陣列預生成法，時間 O(n)，適合 n 較小或需列印每項
int a[1001];
a[0] = 1;
for (int i = 1; i < 1000; i++) a[i] = a[i-1] + i;
// 前 n 項和
int sum = 0;
for (int i = 0; i < n; i++) sum += a[i];

複雜度比較

核心思維：遇到數列求和，**先找差分規律 → 推導通項 → 求和公式化簡**。能將 O(n) 降為 O(1) 是演算法優化的經典樂趣。