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

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

Số Catalan là một 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\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, ...................

Số Catalan có thể thu được cả bằng đệ 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

Ví dụ

# Giải pháp đệ quy
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à lời gọi đệ quy được hiển thị dưới đây.

Cách 2: Phương pháp Quy hoạch động

Ví dụ

# Sử dụng quy hoạch động
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à lời gọi đệ quy được hiển thị dưới đây.

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 ra số Catalan thứ n.