C++ में बाइनोमियल गुणांक

बाइनोमियल गुणांक जिसे c(n,k) या ⁿc_r के रूप में दर्शाया जाता है, (1+X)ⁿ के बाइनोमियल विस्तार में x^k के गुणांक के रूप में परिभाषित किया जाता है।

बाइनोमियल गुणांक उन तरीकों की संख्या का मान भी देता है जिनमें n वस्तुओं में से k वस्तुओं को चुना जाता है यानी n-एलिमेंट सेट के k-कॉम्बिनेशन्स। चयन का क्रम विचार नहीं किया जाता।

यहां, हमें दो पैरामीटर्स 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