C++-এ বাইনোমিয়াল কোএফিশিয়েন্ট

বাইনোমিয়াল কোএফিশিয়েন্টকে c(n,k) বা ⁿc_r দিয়ে ডিনোট করা হয় যা (1+X)ⁿ-এর বাইনোমিয়াল এক্সপ্যানশনে x^k-এর কোএফিশিয়েন্ট হিসেবে ডিফাইন করা হয়।

বাইনোমিয়াল কোএফিশিয়েট আউটসিদে n অবজেক্টের মধ্যে থেকে k আইটেম চুজ করার কতভাবে করা যায় সেটিও বোঝায় (k-কম্বিনেশন অফ n-এলিমেন্ট সেট)। সিলেকশনের অর্ডার কনসিডার করা হয় না।

এখানে, আমাদের দুটি প্যারামিটার n এবং k দেওয়া আছে এবং আমাদের বাইনোমিয়াল কোএফিশিয়েন্ট ⁿc_k -এর ভ্যালু রিটার্ন করতে হবে।

উদাহরণ

ইনপুট: n = 8 এবং k = 3 
আউটপুট: 56

এই সমস্যার একাধিক সমাধান থাকতে পারে,

জেনারেল সমাধান

রিকার্সিভ কল ব্যবহার করে c(n,k)-এর ভ্যালু ক্যালকুলেট করার একটি মেথড রয়েছে। বাইনোমিয়াল কোএফিশিয়েন্টের ভ্যালু বের করার স্ট্যান্ডার্ড ফর্মুলা যা রিকার্সিভ কল ব্যবহার করে:

c(n,k) = c(n-1, k-1) + c(n-1, k)

c(n, 0) = c(n, n) = 1

উপরের ফর্মুলা ব্যবহার করে রিকার্সিভ কল বাস্তবায়ন:

উদাহরণ

#include <iostream> 
using namespace std; 

int binomialCoefficients(int n, int k) { 
    if (k == 0 || k == n) 
        return 1; 
    return binomialCoefficients(n - 1, k - 1) + binomialCoefficients(n - 1, k); 
} 

int main() { 
    int n = 8, k = 5; 
    cout << "The value of C(" << n << ", " << k << ") is " << binomialCoefficients(n, k); 
    return 0; 
}

আউটপুট

The value of C(8, 5) is 56

আরেকটি সমাধান হতে পারে ওভারল্যাপিং সাবপ্রব্লেম ব্যবহার করে। সেজন্য ডাইনামিক প্রোগ্রামিং অ্যালগরিদম ব্যবহার করে সাবপ্রব্লেম এড়ানো যাবে।

উদাহরণ

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

int binomialCoefficients(int n, int k) { 
    int C[k+1]; 
    memset(C, 0, sizeof(C)); 
    C[0] = 1; 
    for (int i = 1; i <= n; i++) { 
        for (int j = min(i, k); j > 0; j--) 
            C[j] = C[j] + C[j-1]; 
    } 
    return C[k]; 
} 

int main() { 
    int n = 8, k = 5; 
    cout << "The value of C(" << n << ", " << k << ") is " << binomialCoefficients(n, k); 
    return 0; 
}

আউটপুট

The value of C(8, 5) is 56