หาผลรวมที่ m ของ n จำนวนธรรมชาติแรกใน C++

โจทย์

ได้รับจำนวนเต็ม m และ n ทางเราต้อง หาผลรวมที่ m ของ n จำนวนธรรมชาติแรก

นิยาม: sum(n, m) คือ การหาผลรวมของ n จำนวนแรก แล้วนำผลรวมนั้นไปเป็น n ใหม่ ทำซ้ำ m รอบ

ตัวอย่าง

Input: m = 4, n = 2

Output: 231

อธิบาย:

sum(2, 4) = sum(sum(2, 3), 1)
          = sum(sum(sum(2, 2), 1), 1)
          = sum(sum(sum(sum(2, 1), 1), 1), 1)
          = sum(sum(sum(3, 1), 1), 1)
          = sum(sum(6, 1), 1)
          = sum(21, 1)
          = 231

แนวทางแก้ปัญหา

ใช้ การเรียกซ้ำ (Recursion):

• ถ้า m = 1: คืนค่า n*(n+1)/2
• ถ้า m > 1: คืนค่า sum(sum(n, m-1), 1) = sum_prev * (sum_prev + 1) / 2

โปรแกรมตัวอย่าง

#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, m = 6;
    cout << m << "-th summation of first " << n << " natural numbers is " << calcSumN(n, m);
    return 0;
}

ผลลัพธ์

6-th summation of first 4 natural numbers is 125230148