एनएच कैटलन नंबर के लिए पायथन प्रोग्राम

इस लेख में, हम nवें कातालान संख्या की गणना के बारे में जानेंगे।

कैटलन नंबर प्राकृतिक संख्याओं का एक क्रम है जो पुनरावर्ती सूत्र द्वारा परिभाषित किया जाता है -

$$C_{0}=1\:और\:C_{n+1}=\displaystyle\sum\limits_{i=0}^n C_{i}C_{n-i} \:n\geq0;$$ के लिए

n =0, 1, 2, 3, … के लिए पहले कुछ कैटलन नंबर 1, 1, 2, 5, 14, 42, 132,429,............ हैं। ....

कैटलन नंबर रिकर्सन और डायनेमिक प्रोग्रामिंग दोनों द्वारा प्राप्त किए जा सकते हैं। तो आइए उनके कार्यान्वयन को देखें।

दृष्टिकोण 1:पुनरावर्तन विधि

उदाहरण

# A recursive solution
def catalan(n):
   #negative value
   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
# main
for i in range(6):
   print (catalan(i))

आउटपुट

1
1
2
5
14
42

सभी चर और पुनरावर्ती कॉल का दायरा नीचे दिखाया गया है।

दृष्टिकोण 2:गतिशील प्रोग्रामिंग विधि

उदाहरण

# using dynamic programming
def catalan(n):
   if (n == 0 or n == 1):
      return 1
   # divide table
   catalan = [0 for i in range(n + 1)]
   # Initialization
   catalan[0] = 1
   catalan[1] = 1
   # recursion
   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]
# main
for i in range (6):
   print (catalan(i),end=" ")

आउटपुट

1
1
2
5
14
42

सभी चर और पुनरावर्ती कॉल का दायरा नीचे दिखाया गया है।

निष्कर्ष

इस लेख में, हमने nth कातालान संख्या उत्पन्न करने की विधि के बारे में सीखा।