Số Catalan thứ n trong Python

Trong bài viết này, chúng ta sẽ học về tính toán số Catalan thứ n.

Số Catalan là dãy số tự nhiên được định nghĩa bởi công thức đệ quy:

$$c_{0} = 1\;and\; c_{n+1} = \displaystyle\sum\limits_{i=0}^n c_{i} c_{n-i}\; for n\geq 0$$

Các số Catalan đầu tiên cho n = 0, 1, 2, 3, ... là 1, 1, 2, 5, 14, 42, 132, 429, ...

Số Catalan có thể đạt được bằng cả đệ quy và quy hoạch động.

Vì vậy hãy xem triển khai của chúng.

Cách 1: Phương pháp đệ quy (Recursion)

Ví dụ

# A recursive solution
def catalan(n):
    # giá trị âm
    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))

Kết quả

1 1 2 5 14 42

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

Cách 2: Phương pháp quy hoạch động (Dynamic Programming)

Ví dụ

# using dynamic programming
def catalan(n):
    if (n == 0 or n == 1):
        return 1
    # chia bảng
    catalan = [0 for i in range(n + 1)]
    # Khởi tạo
    catalan[0] = 1
    catalan[1] = 1
    # đệ quy
    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=" ")

Kết quả

1 1 2 5 14 42

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

Kết luận

Trong bài viết này, chúng ta đã học về phương pháp tạo ra số Catalan thứ n.