C++-এ প্রথম n প্রাকৃতিক সংখ্যার m-তম সামেশন বের করুন

দুটি পূর্ণসংখ্যা m এবং n দেওয়া আছে। প্রথম n প্রাকৃতিক সংখ্যার যোগফল m বার বের করতে হবে (রিকার্সিভলি)।

ডেফিনিশন

• sum(n, 1) = n(n+1)/2 (প্রথম n প্রাকৃতিক সংখ্যার যোগফল)
• sum(n, m) = sum(sum(n, m-1), 1) for m > 1

উদাহরণ

ইনপুট: m = 4, n = 2

আউটপুট: 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

অ্যালগরিদম (রিকার্সিভ)

• বেস কেস: m == 1 → n*(n+1)/2 রিটার্ন।
• রিকার্সিভ কেস: sum(n, m-1) কাল করুন, তার রেজাল্ট দিয়ে আবার sum(result, 1) করুন।

C++ প্রোগ্রাম

#include <iostream>
using namespace std;

int calcSumN(int n, int m) {
    if (m == 1)
        return (n * (n + 1) / 2);
    int prev = calcSumN(n, m - 1);
    return (prev * (prev + 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

ব্যাখ্যা

• প্রতিটি রিকার্সিভ কলে ভ্যালু এক্সপোনেনশিয়ালি বড় হয়।
• m=6, n=4 এর জন্য ফলাফল ১২৫ মিলিয়ন+।
• বড় m,n-এ long long বা BigInteger লাগবে।
• টাইম কমপ্লেক্সিটি: O(m) (রিকার্সিভ কল সংখ্যা)।

ইটারেটিভ ভার্সন

int calcSumNIterative(int n, int m) {
    long long sum = n;
    for (int i = 0; i < m; i++)
        sum = sum * (sum + 1) / 2;
    return sum;
}