C++ प्रोग्राम: पुनरावृत्ति संबंध द्वारा nCr कॉम्बिनेशन गणना

यह C++ प्रोग्राम पुनरावृत्ति संबंध (Recurrence Relation) का उपयोग करके कॉम्बिनेशन nCr (n में से r चुनने के तरीके) की गणना करता है। सूत्र: nCr = n! / (r! × (n-r)!)

एल्गोरिदम

शुरुआत
  1. फंक्शन CalCombination():
     आर्गुमेंट्स: n, r
     बॉडी:
     पुनरावृत्ति संबंध द्वारा कॉम्बिनेशन कैलकुलेट करें:
     nCr = (n/r) × (n-1)C(r-1)
     बेस केस: r=0 होने पर 1 लौटाएं
समाप्ति

उदाहरण कोड

#include <iostream>
using namespace std;

long long CalCombination(long long n, long long r) {
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;
    // समरूपता गुण का उपयोग: nCr = nC(n-r)
    if (r > n - r) r = n - r;
    
    long long result = 1;
    for (long long i = 1; i <= r; i++) {
        result = result * (n - r + i) / i;
    }
    return result;
}

// पुनरावृत्ति संस्करण (मूल कोड के अनुसार)
float CalCombinationRecursive(float n, float r) {
    if (r > 0)
        return (n / r) * CalCombinationRecursive(n - 1, r - 1);
    else
        return 1;
}

int main() {
    long long n, r;
    cout << "Enter the value of n: ";
    cin >> n;
    cout << "Enter the value of r: ";
    cin >> r;
    
    long long res = CalCombination(n, r);
    cout << "\nThe number of possible combinations are: nCr = " << res;
    
    // पुनरावृत्ति संस्करण का डेमो
    cout << "\n\nRecursive version result: " << (int)CalCombinationRecursive(n, r);
    return 0;
}

आउटपुट

Enter the value of n: 7
Enter the value of r: 6
The number of possible combinations are: nCr = 7

Recursive version result: 7

सुधार नोट: मूल कोड में आउटपुट 2 दिखाया गया था जो गलत है (7C6 = 7 होना चाहिए)। पुनरावृत्ति संस्करण में फ्लोटिंग पॉइंट प्रिसिजन इश्यू हो सकता है। मैंने इंटीजर अरिथमेटिक वाला इटरेटिव संस्करण जोड़ा है जो अधिक सटीक और कुशल है।

गुण: nCr = nC(n-r), nC0 = nCn = 1, nC1 = n