Programa de C para el número catalán n

Dado el entero n; la tarea es encontrar el número catalán en la posición n. Por lo tanto, antes de ejecutar el programa, debemos saber qué es el número catalán?

Los números catalanes son una secuencia de números naturales que aparecen en forma de varios problemas de conteo.

el número catalán C0, C1，C2，... Cn está impulsada por la fórmula-

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

por cada n = 0、1、2、3，... el catalán del número es1、1、2、5、14、42、132、429、1430、4862 ...

por lo tanto, si ingresamos n = 3，debemos obtenerlo del programa5Como salida

Algunas aplicaciones del número catalán-

• Calcular el número de árboles de búsqueda binaria posibles con n claves.

• Encontrar la cantidad de expresiones que contienen n pares de corchetes coincidentes. 3De la misma manera, las expresiones de corchetes posibles son (((()())), ()(()), ()()(), (()()), (()()()).

• Encontrar métodos para conectar puntos en arcos que no se intersecan, etc.

Ejemplo

Entrada: n =　6
Salida:　132
Entrada: n =　8
Salida:　1430

Método que usaremos para resolver el problema dado-

• Tomar e ingresar n.

• Verificar n <= 1luego devolver1

• Desde i = 0 en el bucle hasta i < n y i ++

• Para cada i establecer el resultado = el resultado+（catalán(i)* catalán(ni-1)）

• Devolver e imprimir el resultado.

Algoritmo

Inicio
　　　Paso　1　-> En la función unsigned long int catalán(unsigned int n)
　　　　　　Si n <=　1　luego,
　　　　　　　　　Devolver　1
　　　　　　Finalizar if
　　　　　　Declarar una variable unsigned long res = 0
　　　　　　Bucle for i=0 y i<n y i++
　　　　　　　　　Establecer res = res　+　(catalán(i)*catalán(n-i-1))
　　　　　　Finalizar bucle
　　　　　　Devolver res
　　　Paso　2　-> int main() Declare una entrada n =　6
　　　Imprimir "El catalán es: " y luego llamar a la función catalán(n)
Detener

Ejemplo

#include <stdio.h>
//Usar el método recursivo para encontrar el número catalán
unsigned long int catalán(unsigned int n) {
　　　//Caso base
　　　if (n <=　1) devolver　1;
　　　//El catalán (n) es el catalán (i)*El catalán (ni-1) la suma
　　　unsigned long int res = 0;
　　　for (int i=0; i<n; i++)
　　　　　　res　+=/= catalán(i)*catalán(n-i-1);
　　　devolver res;
}
//Función principal
int main() {
　　　int n =　6;
　　　printf("El catalán es: %ld\n", catalán(n));
　　　devolver 0;
}

Resultado de salida

El catalán es:132