algorithm
Algoritmo Numérico Catalán

Algoritmo Numérico Catalán Información Básica

El algoritmo de números catalán es el algoritmo de programación dinámica.

En las matemáticas combinatorias, los números catalanes forman una secuencia de números naturales que ocurren en varios problemas de conteo, que a menudo involucran objetos definidos recursivamente. Los números catalanes en enteros no negativos n son un conjunto de números que surgen en los problemas de enumeración de árboles del tipo, '¿De cuántas maneras se puede dividir un n-gon regular en n-2 triángulos si las diferentes orientaciones se cuentan por separado?'

Aplicación del algoritmo numérico catalán:

1. El número de formas de apilar monedas en una fila inferior que consta de n monedas consecutivas en un plano, de manera que no se permite colocar monedas en los dos lados de las monedas inferiores y cada moneda adicional debe estar por encima de otras dos monedas, es El número n catalán.
2. La cantidad de formas de agrupar una serie de n pares de paréntesis, de manera que cada paréntesis abierto tenga un paréntesis cerrado coincidente, es el número n catalán.
3. La cantidad de formas de cortar un polígono convexo de n + 2 lados en un plano en triángulos conectando vértices con líneas rectas que no se intersectan es el número n catalán. Esta es la aplicación en la que Euler estaba interesado.

Usando una numeración basada en cero, el número n catalán se da directamente en términos de coeficientes binomiales mediante la siguiente ecuación.

Ejemplo de número catalán:

Aquí el valor de n = 4. (Mejor ejemplo: de Wikipedia)

Espacio auxiliar: O(n)
Complejidad del tiempo: O(n^2)

Implementación de 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;
    }
}