Tổng chuỗi cấp số cộng lẻ lồng nhau trong C++

Giới thiệu

Tính tổng dãy: S(n) = 1 + (1+3) + (1+3+5) + ... + (1+3+5+...+(2n-1))

Phân tích toán học

Hàng thứ i: 1 + 3 + 5 + ... + (2i-1) = i² (tổng i số lẻ đầu tiên = i²)

Tổng cần tìm: S(n) = 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6

Chứng minh

Tổng i số lẻ đầu tiên:
1 + 3 + 5 + ... + (2i-1)
= Σ(2k-1) với k=1..i
= 2×Σk - Σ1
= 2×i(i+1)/2 - i
= i(i+1) - i = i²

Mã nguồn hoàn chỉnh (2 phương pháp)

Phương pháp 1: Lặp lồng nhau O(n²)

long long sumSeriesLoop(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        int term = 1;
        for (int j = 1; j <= i; j++) {
            sum += term;
            term += 2;
        }
    }
    return sum;
}

Phương pháp 2: Công thức toán học O(1)

long long sumSeriesFormula(int n) {
    // S(n) = n(n+1)(2n+1)/6
    return 1LL * n * (n + 1) * (2 * n + 1) / 6;
}

Chương trình chính

#include <bits/stdc++.h>
using namespace std;

long long sumSeriesLoop(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        int val = 1;
        for (int j = 1; j <= i; j++) {
            sum += val;
            val += 2;
        }
    }
    return sum;
}

long long sumSeriesFormula(int n) {
    return 1LL * n * (n + 1) * (2 * n + 1) / 6;
}

int main() {
    int n = 35;
    
    cout << "Phuong phap vong lap: " << sumSeriesLoop(n) << endl;
    cout << "Cong thuc toan hoc: " << sumSeriesFormula(n) << endl;
    
    // Kiểm tra n nhỏ
    for (int i = 1; i <= 10; i++) {
        cout << "n=" << i << ": Loop=" << sumSeriesLoop(i) 
             << ", Formula=" << sumSeriesFormula(i) << endl;
    }
    
    return 0;
}

Kết quả chạy chương trình

Phuong phap vong lap: 14910
Cong thuc toan hoc: 14910

n=1: Loop=1, Formula=1
n=2: Loop=5, Formula=5
n=3: Loop=14, Formula=14
n=4: Loop=30, Formula=30
n=5: Loop=55, Formula=55
n=6: Loop=91, Formula=91
n=7: Loop=140, Formula=140
n=8: Loop=204, Formula=204
n=9: Loop=285, Formula=285
n=10: Loop=385, Formula=385

Phân tích độ phức tạp

Ứng dụng

• Tính tổng bình phương: Σi² = n(n+1)(2n+1)/6
• Xác suất, thống kê (phương sai)
• Hình học: thể tích kim tự tháp, v.v.

Kết luận

Bài toán minh họa sức mạnh của suy diễn toán học: biến bài toán O(n²) thành O(1). Luôn tìm công thức đóng (closed-form) trước khi code vòng lặp.