এই নিবন্ধে আমরা n-তম ক্যাটালান সংখ্যা গণনা করার পদ্ধতি শিখব।
ক্যাটালান সংখ্যা হলো প্রাকৃতিক সংখ্যাগুলোর একটি সিকোয়েন্স যা নিচের রিকারসিভ ফর্মুলা দ্বারা ডিফাইন করা হয়:
$$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, ...................
ক্যাটালান সংখ্যা রিকারশন এবং ডাইনামিক প্রোগ্রামিং উভয় দিয়ে প্রাপ্ত করা যায়। তাই তাদের বাস্তবায়ন দেখা যাক।
অপ্রোচ ১: রিকারশন মেথড
উদাহরণ
# একটি রিকারসিভ সমাধান
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
সকল ভেরিয়েবল এবং রিকারসিভ কলের স্কোপ নিচে দেখানো হয়েছে।
অপ্রোচ ২: ডাইনামিক প্রোগ্রামিং মেথড
উদাহরণ
# ডাইনামিক প্রোগ্রামিং ব্যবহার করে
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
সকল ভেরিয়েবল এবং রিকারসিভ কলের স্কোপ নিচে দেখানো হয়েছে।
উপসংহার
এই নিবন্ধে আমরা n-তম ক্যাটালান সংখ্যা জেনারেট করার পদ্ধতি শিখেছি।
