Tổng chuỗi 1 + 2 + 2 + 3 + 3 + 3 + ... + n trong C++

Tính tổng chuỗi mà số i xuất hiện đúng i lần: 1 + 2+2 + 3+3+3 + ... + n (n lần).

Ví dụ

n = 4: 1 + 2+2 + 3+3+3 + 4+4+4+4 = 30.

Phân tích

Chuỗi = 1^2 + 2^2 + 3^2 + ... + n^2.

3 cách giải

Cách 1: 2 vòng lặp lồng (O(n^2))

int calcSeriesSum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            sum += i;
    return sum;
}

Cách 2: 1 vòng lặp (O(n))

int calcSeriesSum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += i * i;
    return sum;
}

Cách 3: Công thức toán học (O(1))

Tổng bình phương: n(n+1)(2n+1)/6.

int calcSeriesSum(int n) {
    return n * (n + 1) * (2 * n + 1) / 6;
}

Cài đặt đầy đủ

#include <iostream>
using namespace std;

int calcSeriesSum(int n) {
    return n * (n + 1) * (2 * n + 1) / 6;
}

int main() {
    int n = 7;
    cout << "Tong chuoi den " << n << " la " << calcSeriesSum(n);
    return 0;
}

Output

Tong chuoi den 7 la 140

So sánh