algorithm
Catalan Number Algorithm

Catalan Number Algorithm Basic Information

L'algoritmo dei numeri catalani è l'algoritmo di programmazione dinamica.

Nella matematica combinatoria, i numeri catalani formano una sequenza di numeri naturali che si verificano in vari problemi di conteggio, spesso con oggetti ricorsivamente definiti. I numeri catalani sugli interi non negativi n sono un insieme di numeri che si presentano nei problemi di enumerazione degli alberi del tipo, 'In quanti modi un n-gon regolare può essere diviso in triangoli n-2 se i diversi orientamenti sono contati separatamente?'

Applicazione dell'algoritmo numerico catalano:

1. Il numero di modi per impilare le monete su una riga in basso che consiste in n monete consecutive in un piano, in modo tale che nessuna moneta possa essere messa sui due lati delle monete in basso e ogni moneta aggiuntiva deve essere sopra altre due monete, è l'ennesimo numero catalano.
2. Il numero di modi per raggruppare una stringa di n coppie di parentesi, in modo tale che ciascuna parentesi aperta abbia una parentesi chiusa corrispondente, è l'ennesimo numero di catalano.
3. Il numero di modi per tagliare un poligono convesso n + 2 in un piano in triangoli collegando i vertici con linee diritte e non intersecanti è l'ennesimo numero catalano. Questa è l'applicazione in cui Eulero era interessato.

Usando la numerazione basata su zero, il n numero catalano viene dato direttamente in termini di coefficienti binomiali secondo la seguente equazione.

Esempio di numero catalano:

Qui valore di n = 4. (Miglior esempio - Da Wikipedia)

Spazio ausiliario: O(n)
Complessità del tempo: O(n^2)

Implementazione C #

public class CatalanNumber
{
    public static int Main(int number)
    {
        int result = 0;
        if (number <= 1) return 1;
        for (int i = 0; i < number; i++)
        {
            result += Main(i)*Main(number - i - 1);
        }
        return result;
    }
}