সি++-এ মটজкин সংখ্যা (Motzkin Number) বের করা

মটজкин সংখ্যা সিরিজ: ১, ১, ৪, ৯, ২১, ৫১, ...

রিকারেন্স রিলেশন:

M₀ = 1, M₁ = 1

Mₙ = ((2n+1)/(n+2)) * Mₙ₋₁ + ((3n-3)/(n+2)) * Mₙ₋₂

উদাহরণ

ইনপুট: n = 5 → আউটপুট: 21

অ্যালগরিদম

n ইনিশিয়ালাইজ করুন।
দুটি ভেরিয়েবল a=1, b=1 রাখুন (M₀, M₁)।
২ থেকে n পর্যন্ত লুপ চালান।
c = ((2*i+1)*b + (3*i-3)*a) / (i+2) বের করুন।
a = b; b = c; আপডেট করুন।
b ফেরত দিন।

সি++ ইমপ্লিমেন্টেশন

#include <bits/stdc++.h>
using namespace std;

int getNthTerm(int n) {
    if (n == 0 || n == 1) return 1;
    int a = 1, b = 1;
    for (int i = 2; i <= n; ++i) {
        int c = ((2 * i + 1) * b + (3 * i - 3) * a) / (i + 2);
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 5;
    cout << getNthTerm(n) << endl; // 21
    return 0;
}