ผลรวมอนุกรม 1 + (1+2) + (1+2+3) + ... + (1+2+...+n) ใน C++

ภาพรวมปัญหา

หาผลรวมของอนุกรมที่พจน์ที่ i คือผลรวมของจำนวนธรรมชาติ i ตัวแรก: 1 + (1+2) + (1+2+3) + ...

ตัวอย่าง

Input: n = 4
Output: 20
Explanation: (1) + (1+2) + (1+2+3) + (1+2+3+4) = 1+3+6+10 = 20

วิธีแก้ปัญหา

วิธี Nested Loop - O(n²)

for i=1 to n:
    for j=1 to i:
        sum += j;

วิธีสูตรคณิตศาสตร์ - O(1)

พจน์ที่ i = i(i+1)/2

ผลรวม = n(n+1)(2n+4)/12 = n(n+1)(n+2)/6

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

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

int main() {
    int n = 7;
    cout << "Sum = " << calcSeriesSum(n);
    return 0;
}

ผลลัพธ์

Sum of the series 1 + (1+2) + ... + (1+2+...+7) is 84