পাইথন প্রোগ্রামে Nth কাতালান নম্বর

এই নিবন্ধে, আমরা nম কাতালান সংখ্যা গণনা সম্পর্কে শিখব।

কাতালান সংখ্যা প্রাকৃতিক সংখ্যার একটি ক্রম যা পুনরাবৃত্তিমূলক সূত্র দ্বারা সংজ্ঞায়িত করা হয় −

$$c_{0} =1\;এবং\; c_{n+1} =\displaystyle\sum\limits_{i=0}^nc_{i} c_{n-i}\; n\geq 0;$$

n =0, 1, 2, 3, … এর জন্য প্রথম কয়েকটি কাতালান সংখ্যা হল 1, 1, 2, 5, 14, 42, 132, 429,................ ...

কাতালান সংখ্যাগুলি পুনরাবৃত্তি এবং গতিশীল প্রোগ্রামিং উভয় দ্বারা প্রাপ্ত করা যেতে পারে।

তাহলে আসুন তাদের বাস্তবায়ন দেখি।

পদ্ধতি 1:পুনরাবৃত্তি পদ্ধতি

উদাহরণ

পদ্ধতি 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

সমস্ত ভেরিয়েবল এবং রিকার্সিভ কলের সুযোগ নীচে দেখানো হয়েছে৷

উপসংহার

এই নিবন্ধে, আমরা nম কাতালান সংখ্যা