Cài đặt thuật toán Catalan Number trong lập trình

Trong toán học, số Catalan là một dãy số tự nhiên xuất hiện trong nhiều bài toán tổ hợp, đa giác, chuỗi ngoặc và cấu trúc dữ liệu. Thuật toán Catalan có công thức đệ quy và công thức đóng, giúp chúng ta dễ dàng tính toán các số trong dãy này.

Các công thức tính số Catalan:

1. Công thức đệ quy: Số ( C_n ) có thể được tính bằng công thức đệ quy như sau: [ C_0 = 1 \ C_{n} = \sum_{i=0}^{n-1} C_i \cdot C_{n-i-1} , \text{với}, n \ge 1 ]

2. Công thức đóng: Số ( C_n ) cũng có thể được biểu diễn dưới dạng công thức đóng: [ C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!} ]

Cách cài đặt thuật toán trong lập trình

1. Sử dụng Python:

Chúng ta có thể viết hàm tính số Catalan bằng cách sử dụng cả hai công thức trên. Sau đây là các ví dụ minh họa:

Cách 1: Sử dụng công thức đệ quy

def catalan_recursive(n):
    if n == 0:
        return 1
    res = 0
    for i in range(n):
        res += catalan_recursive(i) * catalan_recursive(n - i - 1)
    return res

# Ví dụ sử dụng
n = 5
print(catalan_recursive(n))

Cách 2: Sử dụng công thức đóng

def factorial(num):
    if num == 0 or num == 1:
        return 1
    res = 1
    for i in range(2, num + 1):
        res *= i
    return res

def catalan_closed(n):
    return factorial(2 * n) // (factorial(n + 1) * factorial(n))

# Ví dụ sử dụng
n = 5
print(catalan_closed(n))

2. Sử dụng C++:

Dưới đây là cách cài đặt thuật toán tính số Catalan trong C++.

Cách 1: Sử dụng công thức đệ quy

#include<iostream>
using namespace std;

unsigned long int catalan(unsigned int n) {
    if (n <= 1)
        return 1;
    unsigned long int res = 0;
    for (int i = 0; i < n; i++)
        res += catalan(i) * catalan(n - i - 1);
    return res;
}

int main() {
    int n = 5;
    cout << catalan(n);
    return 0;
}

Cách 2: Sử dụng công thức đóng

#include<iostream>
using namespace std;

unsigned long int factorial(unsigned int n) {
    if (n == 0 || n == 1)
        return 1;
    unsigned long int res = 1;
    for (int i = 2; i <= n; i++)
        res *= i;
    return res;
}

unsigned long int catalan(unsigned int n) {
    unsigned long int res = factorial(2 * n) / (factorial(n + 1) * factorial(n));
    return res;
}

int main() {
    int n = 5;
    cout << catalan(n);
    return 0;
}

Cả hai ngôn ngữ đều thể hiện rõ ràng cách tính số Catalan bằng các công thức đã đề cập. Việc lựa chọn cách cài đặt phụ thuộc vào yêu cầu cụ thể của bài toán và hiệu suất mong muốn. Dùng công thức đệ quy tuy dễ hiểu nhưng không hiệu quả cho các giá trị lớn của ( n ), trong khi đó công thức đóng thì nhanh và hiệu quả hơn nhưng lại yêu cầu tính toán giai thừa chính xác.

Ứng dụng của số Catalan

Số Catalan có nhiều ứng dụng rộng rãi trong các bài toán tổ hợp như:

• Tạo cây nhị phân tìm kiếm với ( n ) nút.
• Tạo các dãy ngoặc đúng với ( n ) cặp ngoặc.
• Sắp xếp tam giác.
• Phân hoạch tập hợp.

Việc hiểu và cài đặt thành thạo thuật toán Catalan là một kỹ năng quan trọng trong lập trình và toán học tổ hợp, mang lại nền tảng vững chắc để giải quyết nhiều bài toán phức tạp hơn.