Tìm tổng thứ m của n số tự nhiên đầu tiên trong C++

Cho hai số nguyên m và n. Nhiệm vụ: Tìm tổng thứ m của n số tự nhiên đầu tiên.

Mô tả: Tính tổng của tổng của n số tự nhiên, lặp lại m lần.

Công thức:

Nếu (m > 1): sum(n, m) = sum( sum(n, (m-1)), 1 )

Nếu (m = 1): sum(n, m) = sum(n, 1) = tổng n số tự nhiên

Ví dụ:

Đầu vào: m = 4, n = 2

Đầu ra: 231

Giải thích:

sum(2, 4) = sum ( sum(2, 3), 1 ) = ... = 231

Phương pháp giải

Dùng hai vòng lặp lồng nhau hoặc đệ quy hiệu quả hơn.

Thuật toán:

Bước 1: Cập nhật sum = sum(n, m-1) * (sum(n, m-1) + 1) / 2 nếu m > 1.

Bước 2: Nếu m = 1, trả về sum = n * (n+1) / 2.

Bước 3: Trả về sum.

Chương trình minh họa

Ví dụ

#include <iostream>
using namespace std;

int calcSumN(int n, int m) {
    if (m == 1)
        return (n * (n + 1) / 2);
    return (calcSumN(n, m - 1) * (calcSumN(n, m - 1) + 1) / 2);
}

int main() {
    int n = 4;
    int m = 6;
    cout << m << "-th summation of first " << n << " natural numbers is " << calcSumN(n, m);
    return 0;
}

Kết quả

6-th summation of first 4 natural numbers is 125230148