Chương trình Python cho số Catalan thứ n

Trong bài viết này, chúng ta sẽ tìm hiểu về cách tính số Catalan thứ n.

Số Catalan là một dãy số tự nhiên được xác định bằng công thức đệ quy -

$$ C_ {0} =1 \:và \:C_ {n + 1} =\ displaystyle \ sum \ limit_ {i =0} ^ n C_ {i} C_ {n-i} cho \:n \ geq0; $$

Một vài số Catalan đầu tiên cho n =0, 1, 2, 3,… là 1, 1, 2, 5, 14, 42, 132,429, ............... ....

Có thể lấy số Catalan bằng cả lập trình đệ quy và lập trình động.

Cách tiếp cận 1:Phương pháp đệ quy

Ví dụ

# 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))

Đầu ra

1
1
2
5
14
42

Phạm vi của tất cả các biến và lệnh gọi đệ quy được hiển thị bên dưới.

Cách tiếp cận 2:Phương pháp lập trình động

Ví dụ

# 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=" ")

Đầu ra

1
1
2
5
14
42

Phạm vi của tất cả các biến và lệnh gọi đệ quy được hiển thị bên dưới.

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về phương pháp tạo số Catalan thứ n.