ক্যাটালান নম্বর: c₀=1, cₙ₊₁ = Σ cᵢcₙ₋ᵢ (i=0 থেকে n)। প্রথম কয়েকটি: 1, 1, 2, 5, 14, 42, 132, 429,...
পদ্ধতি ১: রিকার্শন
def catalan(n):
if n <= 1:
return 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_arr = [0] * (n + 1)
catalan_arr[0] = catalan_arr[1] = 1
for i in range(2, n + 1):
catalan_arr[i] = 0
for j in range(i):
catalan_arr[i] += catalan_arr[j] * catalan_arr[i-j-1]
return catalan_arr[n]
for i in range(6):
print(catalan(i), end=" ")
আউটপুট
1 1 2 5 14 42
উপসংহার
রিকার্শন এবং ডাইনামিক প্রোগ্রামিং (বটম-আপ) দিয়ে n-তম ক্যাটালান নম্বর বের করা।
