द्विपद गुणांक c(n,k) या n . के रूप में दर्शाया गया है ग<उप>आर x k . के गुणांक के रूप में परिभाषित किया गया है (1+X) n . के द्विपद विस्तार में ।
द्विपद गुणांक उन तरीकों की संख्या का भी मान देता है जिनमें k वस्तुओं को n वस्तुओं में से चुना जाता है अर्थात n-तत्व सेट के k-संयोजन। मदों के चयन के क्रम पर विचार नहीं किया गया।
यहां, हमें दो पैरामीटर n और k दिए गए हैं और हमें द्विपद गुणांक का मान वापस करना होगा n ग<उप>के ।
उदाहरण
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