কম্পিউটার

পাইথন প্রোগ্রামে 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

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

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

পদ্ধতি 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 কাতালান নম্বর

উপসংহার

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

তৈরি করার পদ্ধতি সম্পর্কে শিখেছি
  1. ফিবোনাচ্চি সিরিজের একটি সংখ্যার nম গুণের জন্য পাইথন প্রোগ্রাম

  2. আর্মস্ট্রং নম্বর চেক করতে পাইথন প্রোগ্রাম

  3. পাইথন প্রোগ্রামে N-তম ফিবোনাচি নম্বর

  4. nম কাতালান নম্বরের জন্য পাইথন প্রোগ্রাম