দ্বিপদ সহগ c(n,k) বা n হিসাবে চিহ্নিত cr x k এর সহগ হিসাবে সংজ্ঞায়িত করা হয় দ্বিপদী সম্প্রসারণে (1+X) n .
দ্বিপদী সহগ n বস্তুর মধ্য থেকে k আইটেমগুলি যেমন n-উপাদান সেটের k-সংমিশ্রণগুলি বেছে নেওয়া হয় তার সংখ্যার মানও দেয়। আইটেম নির্বাচনের ক্রম বিবেচনা করা হয় না।
এখানে, আমাদের দুটি প্যারামিটার দেওয়া হয়েছে n এবং k এবং আমাদের দ্বিপদ সহগের মান ফেরত দিতে হবে n ck .
উদাহরণ
Input : n = 8 and k = 3 Output : 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
