C प्रोग्राम: nth कैटालन संख्या

कैटालन संख्याएं क्या हैं?

कैटालन संख्याएं प्राकृतिक संख्याओं का एक अनुक्रम है जो कई गणना समस्याओं में प्रकट होता है।

सूत्र

Cₙ = (1/(n+1)) × (2n)! / (n! × n!) = (2n)! / ((n+1)! × n!)

पहली कुछ कैटालन संख्याएं

n:  0  1  2  3  4   5   6    7     8      9      10
Cₙ: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796

अनुप्रयोग

• n कुंजियों के साथ संभावित बाइनरी सर्च ट्री की संख्या
• n जोड़ी कोष्ठकों के सही ढंग से मिलान वाले व्यंजक (n=3 के लिए: ((())), ()(()), ()()(), (())(), (()()))
• वृत्त पर बिंदुओं को असंयुक्त तारों से जोड़ने के तरीके
• ग्रिड पथ जो विकर्ण को पार नहीं करते
• स्टैक क्रमपरिवर्तन

रिकर्सिव दृष्टिकोण

Cₙ = Σ Cᵢ × Cₙ₋ᵢ₋₁ (i=0 से n-1 तक)

बेस केस: C₀ = C₁ = 1

C प्रोग्राम (रिकर्सिव)

#include <stdio.h>

unsigned long long catalan(unsigned int n) {
    if (n <= 1) return 1;
    
    unsigned long long res = 0;
    for (int i = 0; i < n; i++)
        res += catalan(i) * catalan(n - i - 1);
    return res;
}

int main() {
    int n;
    printf("n दर्ज करें (0-20): ");
    scanf("%d", &n);
    
    if (n < 0 || n > 20) {
        printf("सीमा 0-20 के बाहर\n");
        return 1;
    }
    
    printf("कैटालन(%d) = %llu\n", n, catalan(n));
    return 0;
}

आउटपुट

n दर्ज करें: 6
कैटालन(6) = 132

कुशल दृष्टिकोण (डायनामिक प्रोग्रामिंग)

unsigned long long catalan_dp(int n) {
    unsigned long long cat[n + 1];
    cat[0] = cat[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        cat[i] = 0;
        for (int j = 0; j < i; j++)
            cat[i] += cat[j] * cat[i - j - 1];
    }
    return cat[n];
}

सीधा सूत्र दृष्टिकोण (सबसे तेज़)

unsigned long long catalan_direct(int n) {
    unsigned long long res = 1;
    for (int i = 0; i < n; i++) {
        res = res * (2 * n - i) / (i + 1);
    }
    return res / (n + 1);
}

जटिलता तुलना