algorithm
कैटलन संख्या एल्गोरिदम

कैटलन संख्या एल्गोरिथम बुनियादी जानकारी

कैटलन संख्या एल्गोरिथ्म डायनेमिक प्रोग्रामिंग एल्गोरिथम है।

कॉम्बीनेटरियल गणित में, कैटलन संख्याएं प्राकृतिक संख्याओं का एक क्रम बनाती हैं जो विभिन्न गिनती समस्याओं में होती हैं, जिसमें अक्सर पुनरावर्ती-परिभाषित ऑब्जेक्ट शामिल होते हैं। Nonnegative पूर्णांक n पर कैटलन संख्याएँ संख्याओं का एक समूह है जो पेड़ के प्रकार की समस्याओं में उत्पन्न होती हैं, 'कितने तरीकों से एक नियमित n-gon को n-2 त्रिकोणों में विभाजित किया जा सकता है यदि अलग-अलग झुकावों को अलग-अलग गिना जाता है?'

कैटलन संख्या एल्गोरिथम का अनुप्रयोग:

1. एक तल पर सिक्कों को ढेर करने के तरीकों की संख्या जिसमें एक विमान में लगातार लगातार सिक्के होते हैं, जैसे कि किसी भी सिक्के को नीचे के सिक्कों के दोनों किनारों पर डालने की अनुमति नहीं है और प्रत्येक अतिरिक्त सिक्के को दो अन्य सिक्कों से ऊपर होना चाहिए, एनटी कैटलन नंबर।
2. कोष्ठकों के n जोड़े की एक स्ट्रिंग को समूहित करने के तरीकों की संख्या, जैसे कि प्रत्येक खुले कोष्ठक में एक मिलान बंद कोष्ठक है, nth कैटलन संख्या है।
3. सीधे, गैर-अन्तर्विभाजक लाइनों के साथ जोड़कर त्रिकोण में एक विमान में n + 2-पक्षीय उत्तल बहुभुज को काटने के तरीकों की संख्या nth कैटलॉग संख्या है। यह वह आवेदन है जिसमें यूलर रुचि रखते थे।

शून्य-आधारित नंबरिंग का उपयोग करते हुए, n वें कैटलन नंबर को निम्नलिखित समीकरण द्वारा द्विपद गुणांक के संदर्भ में सीधे दिया जाता है।

कैटलन संख्या का उदाहरण:

यहाँ n = 4. का मूल्य (सर्वोत्तम उदाहरण - विकिपीडिया से)

सहायक स्थान: O(n)
समय जटिलता: O(n^2)

C # कार्यान्वयन

public class CatalanNumber
{
    public static int Main(int number)
    {
        int result = 0;
        if (number <= 1) return 1;
        for (int i = 0; i < number; i++)
        {
            result += Main(i)*Main(number - i - 1);
        }
        return result;
    }
}