Module: Numeri catalani

Problem

1 /2

Dove ricorrono i numeri catalani?

-Numero di psp con un determinato numero di coppie di parentesi

-Numero di alberi binari con un determinato numero di foglie

-Numero di percorsi dall'angolo in basso a sinistra all'angolo in alto a destra nel quadrato n * n che non toccano la diagonale

-Numero di divisioni di n-gon in triangoli

Come contare?

1) Formula per l'ennesimo numero catalano:

2)
•Otteniamo un PSS di lunghezza 2n

•Ovviamente inizia con una parentesi graffa aperta

•Quindi, diciamo P = (A)B, dove A e B – anche psp (inoltre, A e B possono essere vuoti)

•Se la lunghezza di A = 2k, allora la sequenza A può essere composta nei modi Ck

•Allora la lunghezza di B = 2(n – k - 1) e B può essere composta nei modi Cn-k-1

•Vediamo la formula per dp: Cn = sum(Ck * Cn-k-1) per tutti i k <

Materiali usati:

Output N-esimo numero di catalano

Input

La prima riga dell'input contiene un singolo numero N (\(1 <= N <= 20\)) .

Uscita

Stampa un numero - Nnumero del catalano

#	Input	Uscita
1	1	1

Attach a file with the source code of the program:

or select a programming language and type your program

Auto