Module: số tiếng Catalan


Problem

1 /2


Số số Catalan

Theory Click to read/hide

Các số Catalan xuất hiện ở đâu?
 

-Số psp với một số cặp dấu ngoặc nhất định
-Số cây nhị phân với số lá cho trước
-Số đường dẫn từ góc dưới bên trái lên góc trên bên phải trong hình vuông thứ n * n không chạm vào đường chéo

-Số lần chia n-giác thành tam giác



Cách đếm?
 
1) Công thức cho số Catalan thứ n:



2)
•Hãy có một PSS dài 2n
•Rõ ràng là nó bắt đầu bằng một dấu ngoặc mở
•Vì vậy, giả sử P = (A)B, trong đó A và B – cả psp (hơn nữa, A và B có thể để trống)
•Nếu độ dài của A = 2k thì dãy A có thể được lập theo Ck cách
•Sau đó, độ dài của B = 2(n – k - 1) và B có thể được tạo thành theo các cách Cn-k-1

Problem

Xuất N-số thứ của tiếng Catalan

Đầu vào
Dòng đầu tiên của dữ liệu nhập chứa một số duy nhất N (\(1 <= N <= 20\)) .
 
Đầu ra
In một số - Nsố của tiếng Catalan
 

 

Ví dụ
<đầu>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Đầu vào Đầu ra
1 1 1