इस लेख में, हम nth कैटलन नंबर की गणना के बारे में सीखेंगे।
कैटलन नंबर्स प्राकृतिक संख्याओं का एक क्रम है जो रिकर्सिव फॉर्मूला द्वारा परिभाषित है:
c₀ = 1 और cₙ₊₁ = Σᵢ₌₀ⁿ cᵢ cₙ₋ᵢ n ≥ 0 के लिए
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 कैटलन नंबर जनरेट करने की विधि के बारे में सीखा।
