Tổng dãy số cho trước trong C++

Cho n, k. Tính tổng:

(1*2*...*k) + (2*3*...*(k+1)) + ... + ((n-k+1)*...*(n))

Ví dụ

n = 4, k = 3: (1*2*3) + (2*3*4) = 6 + 24 = 30.

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

int findSeriesSum(int n, int k) {
    int sum = 0;
    for (int i = 1; i <= n - k + 1; i++) {
        int term = 1;
        for (int j = i; j < i + k; j++) term *= j;
        sum += term;
    }
    return sum;
}

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

Tổng = (n+1) * n * (n-1) * ... * (n-k+1) / (k+1).

Chứng minh: Mỗi hạng i(i+1)...(i+k-1) = (i+k-1)! / (i-1)! = k! * C(i+k-1, k). Tổng tổ hợp có công thức gọn.

int findSeriesSum(int n, int k) {
    long long sum = 1;
    for (int i = n + 1; i > n - k; i--) sum *= i;
    sum /= (k + 1);
    return sum;
}

Cài đặt đầy đủ

#include <iostream>
using namespace std;

int findSeriesSum(int n, int k) {
    long long sum = 1;
    for (int i = n + 1; i > n - k; i--) sum *= i;
    sum /= (k + 1);
    return sum;
}

int main() {
    int n = 4, k = 3;
    cout << "Tong day so la " << findSeriesSum(n, k);
    return 0;
}

Output

Tong day so la 30

So sánh