Số Catalan thứ N trong Chương trình Python

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} ^ nc_ {i} c_ {n-i} \; cho n \ geq 0; $$

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

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

Vì vậy, hãy xem việc triển khai của họ.

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

Ví dụ

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

# 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