Chương trình C tính số Catalan thứ n

Cho số nguyên n, tìm số Catalan tại vị trí thứ n.

Số Catalan là dãy số tự nhiên xuất hiện trong nhiều bài toán tổ hợp.

Công thức: Cₙ = (1/(n+1)) * C(2n, n) = (2n)! / ((n+1)! n!)

Dãy Catalan đầu tiên: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

Ứng dụng:

• Đếm số cây tìm kiếm nhị phân với n khóa.
• Số biểu thức ngoặc đúng với n cặp ngoặc.
• Số cách nối các điểm trên đường tròn bằng dây không giao nhau.

Ví dụ

Input: n = 6 → Output: 132
Input: n = 8 → Output: 1430

Phương pháp đệ quy:

• Nếu n ≤ 1 trả về 1.
• Khác: Cₙ = Σ Cᵢ * Cₙ₋ᵢ₋₁ với i từ 0 đến n-1.

Mã nguồn C

#include <stdio.h>

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 = 6;
    printf("Số Catalan thứ %d là: %ld\n", n, catalan(n));
    return 0;
}

Kết quả

Số Catalan thứ 6 là: 132