एक इंटरगर दिया गया n; कार्य उस nवें स्थान पर कातालान संख्या का पता लगाना है। इसलिए, प्रोग्राम करने से पहले हमें पता होना चाहिए कि कैटलन नंबर क्या है?
कैटलन संख्या प्राकृतिक संख्याओं का अनुक्रम है, जो विभिन्न गिनती संख्या समस्याओं के रूप में होती है।
कैटलन संख्याएँ C0, C1, C2,… Cn सूत्र द्वारा संचालित हैं -
$$c_{n}=\frac{1}{n+1}\binom{2n}{n} =\frac{2n!}{(n+1)!n!}$$
प्रत्येक n =0, 1, 2, 3, ... के लिए कुछ कैटलन संख्याएं हैं 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...
इसलिए यदि हम n =3 दर्ज करते हैं तो हमें प्रोग्राम से आउटपुट के रूप में 5 प्राप्त करना चाहिए
कैटलन नंबरों के कुछ अनुप्रयोगों में से कुछ -
- n कुंजियों के साथ संभावित बाइनरी सर्च ट्री की संख्या की गणना करना।
- कोष्ठक के n युग्म वाले व्यंजकों की संख्या ज्ञात करना जो सही सुमेलित हैं। जैसे n =3 के लिए संभावित कोष्ठक व्यंजक ((())), ()(()), ()()(), (())(), (()()) होगा।
- सर्कल असंबद्ध जीवाओं पर बिंदु को जोड़ने के तरीकों की संख्या ढूँढना, और भी बहुत कुछ।
उदाहरण
Input: n = 6 Output: 132 Input: n = 8 Output: 1430
दृष्टिकोण हम दी गई समस्या को हल करने के लिए उपयोग करेंगे -
- टेकिंग और इनपुट एन.
- जांचें कि n <=1 तो, 1 लौटाएं
- i=0 से i
- प्रत्येक i सेट परिणाम के लिए =परिणाम + (कातालान(i)*catalan(n-i-1))
- परिणाम लौटाएं और प्रिंट करें।
एल्गोरिदम
Start Step 1 -> In function unsigned long int catalan(unsigned int n) If n <= 1 then, Return 1 End if Declare an unsigned long variable res = 0 Loop For i=0 and i<n and i++ Set res = res + (catalan(i)*catalan(n-i-1)) End Loop Return res Step 2 -> int main() Declare an input n = 6 Print "catalan is : then call function catalan(n) Stop
उदाहरण
#include <stdio.h>
// using recursive approach to find the catalan number
unsigned long int catalan(unsigned int n) {
// Base case
if (n <= 1) return 1;
// catalan(n) is sum of catalan(i)*catalan(n-i-1)
unsigned long int res = 0;
for (int i=0; i<n; i++)
res += catalan(i)*catalan(n-i-1);
return res;
}
//Main function
int main() {
int n = 6;
printf("catalan is :%ld\n", catalan(n));
return 0;
} आउटपुट
catalan is :132