इस लेख में, हम nth कैटलन संख्या की गणना के बारे में जानेंगे।
कैटलन संख्याएं प्राकृतिक संख्याओं का एक क्रम है जिसे पुनरावर्ती सूत्र द्वारा परिभाषित किया जाता है -
$$C_{0}= 1\:and\:C_{n+1}=\displaystyle\sum\limits_{i=0}^n C_{i}C_{n-i} for \:n\geq0;$$
n = 0, 1, 2, 3, ... के लिए पहली कुछ कैटलन संख्याएं 1, 1, 2, 5, 14, 42, 132, 429, ................... हैं
कैटलन संख्याएं रिकर्सन और डायनामिक प्रोग्रामिंग दोनों द्वारा प्राप्त की जा सकती हैं। तो आइए उनके कार्यान्वयन को देखते हैं।
दृष्टिकोण 1: रिकर्सन विधि
उदाहरण
# एक पुनरावर्ती समाधान
def catalan(n):
# ऋणात्मक मान
if n <= 1:
return 1
# Catalan(n) = catalan(i)*catalan(n-i-1)
res = 0
for i in range(n):
res += catalan(i) * catalan(n-i-1)
return res
# मेन
for i in range(6):
print(catalan(i))
आउटपुट
1 1 2 5 14 42
सभी वेरिएबल्स और पुनरावर्ती कॉल का स्कोप नीचे दिखाया गया है।
दृष्टिकोण 2: डायनामिक प्रोग्रामिंग विधि
उदाहरण
# डायनामिक प्रोग्रामिंग का उपयोग करके
def catalan(n):
if (n == 0 or n == 1):
return 1
# टेबल विभाजित करें
catalan = [0 for i in range(n + 1)]
# इनिशियलाइज़ेशन
catalan[0] = 1
catalan[1] = 1
# पुनरावृत्ति
for i in range(2, n + 1):
catalan[i] = 0
for j in range(i):
catalan[i] = catalan[i] + catalan[j] * catalan[i-j-1]
return catalan[n]
# मेन
for i in range(6):
print(catalan(i), end=" ")
आउटपुट
1 1 2 5 14 42
सभी वेरिएबल्स और पुनरावर्ती कॉल का स्कोप नीचे दिखाया गया है।
निष्कर्ष
इस लेख में, हमने nth कैटलन संख्या उत्पन्न करने की विधि के बारे में सीखा।
