Chương trình C/C++ số Catalan 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, thường liên quan đến đối tượng đệ quy.

• Cₙ là số từ Dyck độ dài 2n (chuỗi n X và n Y, không có đoạn đầu nào Y nhiều hơn X). Ví dụ n=3: XXXYYY, XYXXYY, XYXYXY, XXYYXY, XXYXYY.
• Đổi X thành '(' và Y thành ')', Cₙ đếm số biểu thức ngoặc đúng n cặp: ((())), ()(()), ()()(), (())(), (()()).
• Cₙ là số cách đặt ngoặc hoàn toàn cho n+1 nhân tử (số cách liên kết n phép toán nhị phân). n=3: ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).
• Cây nhị phân đầy đủ: Cₙ là số cây nhị phân đầy đủ n+1 lá.

Ví dụ

Đầu vào - 6
Đầu ra - 1 1 2 5 14 42

Giải thích: Các số Catalan đầu tiên (n=0..10): 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862...

Ví dụ

#include <iostream>
using namespace std;

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

int main(){
    for (int i=0; i<6; i++)
        cout << catalan(i) << " ";
    return 0;
}

Kết quả

1 1 2 5 14 42