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

Cho một interger n; nhiệm vụ là tìm Số Catalan ở vị trí thứ n đó. Vì vậy, trước khi thực hiện chương trình, chúng ta phải biết Số Catalan là gì?

Số catlan là dãy số tự nhiên, xuất hiện dưới dạng các bài toán số đếm khác nhau.

Các số Catalan C0, C1, C2,… Cn được định hướng bởi công thức -

$$ c_ {n} =\ frac {1} {n + 1} \ binom {2n} {n} =\ frac {2n!} {(n + 1)! n!} $$

Một vài số Catalan cho mỗi n =0, 1, 2, 3,… là 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…

Vì vậy, nếu chúng tôi nhập n =3, chúng tôi sẽ nhận được 5 làm đầu ra từ chương trình

Một số ứng dụng của số Catalan -

• Đếm số lượng cây tìm kiếm nhị phân có thể có với n khóa.
• Tìm số biểu thức chứa n cặp ngoặc được ghép đúng. Giống như đối với n =3, biểu thức dấu ngoặc có thể có sẽ là ((())), () (()), () () (), (()) (), (() ()).
• Tìm nhiều cách để kết nối điểm trên các hợp âm rời rạc trong vòng kết nối và nhiều cách khác.

Ví dụ

 Đầu vào:n =6 Đầu ra:132 Đầu vào:n =8 Đầu ra:1430 

Phương pháp tiếp cận mà chúng tôi sẽ sử dụng để giải quyết vấn đề đã cho -

• Lấy và nhập n.
• Kiểm tra Nếu n <=1 thì Trả về 1
• Vòng lặp từ i =0 đến i
• Với mọi tôi Đặt kết quả =result + (catalan (i) * catalan (n-i-1))
• Trả lại và in kết quả.

Thuật toán

 Bắt đầu Bước 1 -> Trong hàm unsigned long int catalan (unsigned int n) Nếu n <=1 thì Trả về 1 Kết thúc nếu Khai báo biến dài không dấu res =0 Vòng lặp Đối với i =0 và i  int main () Khai báo đầu vào n =6 In "catalan là:sau đó gọi hàm catalan (n) Stop  
 Ví dụ 
 
 #include  // sử dụng phương pháp đệ quy để tìm số catalan long int catalan (unsigned int n) {// Trường hợp cơ sở if (n <=1) return 1; // catalan (n) là tổng của catalan (i) * catalan (n-i-1) unsigned long int res =0; for (int i =0; i  
 Đầu ra 
 
 tiếng catalan là:132