PROBLEMA
No sé si el ejercicio está planteado para usar específicamente factoriales para su cálculo. Sin embargo, uno de los problemas al trabajar con valores factoriales es que pronto nos acabamos el tamaño en memoria máximo para almacenarlos.
Los números de Catalan, son una secuencia de números naturales muy usados en combinatoria. Los mismos se pueden calcular mediante la siguiente fórmula (tomado de Wikipedia):

Sin embargo, los números de Catalan también cumplen la siguiente propiedad o relación de recurrencia:

La cual podemos re escribir de la siguiente forma como una fórmula recursiva:

Cn = 1; para n = 0;
Cn = (2(2n - 1) / (n + 1))*Cn-1; para n > 0
Los siguientes tres planteamientos a continuación, nos permiten calcular los primeros 34 valores de Catalan usando el tipo unsigned long long int
. Para valores superiores, la representación queda fuera de rango, por lo cual tendríamos que usar librerías de enteros grandes (Big Integer).
Solución Recursiva
Podemos calcular el n-ésimo
número de Catalan, usando esta forma recursiva que no implica el cálculo de factoriales y que en términos de costo computacional es mejor. Por otro lado, debido a las magnitudes representadas por valores de n
superiores a 25, podemos usar un tipo entero unsigned long long int
(C++ 11) que son valores en la escala del 0 al 18,446,744,073,709,551,615.
Por ejemplo:
unsigned long long int catalan(unsigned long long int n)
{
if (n == 0)
{
return 1;
}
else
{
return (((4 * n) - 2) * catalan(n - 1) / (n + 1));
}
}
Notemos que la fórmula recursiva introduce el valor de catalan(n - 1)
:
(4 * n) - 2) * catalan(n - 1)
como parte del cálculo del numerador, esto para evitar que el programa calcule y trunque por defecto el primer operando que se ve en la fórmula de recursión mostrada en la imagen:
((4 * n) - 2) / (n + 1)) * catalan(n - 1) // escribir así la fórmula produce resultados no esperados
La recursión usada puede afectar el rendimiento cuando el valor a calcular es demasiado alto. Este algoritmo tiene una complejidad O(n^2) (cuadrática).
Solución dinámica (iterativa)
Podemos usar la técnica de memoización para mejorar la eficiencia del algoritmo anterior, pero aunque ganamos en términos de velocidad para obtener un valor nuevo basado en el que ha sido previamente calculado, siempre tendremos que realizar una primera ejecución para almacenar los valores de 1
a n - 1
antes de obtener n
.
La mejora implica crear algún tipo de estructura para almacenar los valores calculados y a partir de los mismos obtener el siguiente. Esto nos elimina el problema de la recursión y simplemente convierte el algoritmo en uno iterativo.
Por ejemplo, podemos hacer algo parecido a lo siguiente para calcular los primeros n
números de Catalan:
std::vector<unsigned long long int> iterativeCatalan(const std::vector<unsigned long long int> &lista)
{
std::vector<unsigned long long int> valores;
valores.push_back((unsigned long long int)1);
for (int i = 1; i <= lista.size(); ++i)
{
unsigned long long int valor = (((4 * i) - 2) * valores[i - 1] / (i + 1));
valores.push_back((unsigned long long int)valor);
}
return valores;
}
En el código anterior se calculan los números de Catalan basándose exclusivamente en el valor previamente almacenado en la lista (en la posición anterior). La lista se inicia con el primer elemento establecido a 1.
Esta solución también tiene complejidad O(n^2), pero como dije en un principio podemos aprovechar que hemos almacenado los valores previos y podemos calcular los siguientes a partir de los ya almacenados. Además, no implica un proceso de recursión.
Solución usando una fórmula combinatoria
Tal vez en términos de eficiencia esta sea una opción más aconsejable, y es que si logramos obtener el valor del coeficiente binomial representado por C(2n, n)
en la fórmula del número de Catalan Cn
, entonces la complejidad de nuestro algoritmo será simplemente O(n), que es bastante mejor que las anteriores.
Lo que debemos hacer es plantear una fórmula para calcular el valor de C(2n, n)
: combinación sin repetición de n
elementos, con n < 2n
(claramente), elegidos entre los 2n
.
Una forma de hacerlo sería:
// cálculo del coeficiente Binomial
unsigned long long int coeficienteBinomial(int n, int k)
{
unsigned long long int resultado = 1;
if (k > n - k)
{
k = n - k;
}
for (int i = 0; i < k; ++i)
{
resultado *= (n - i);
resultado /= (i + 1);
}
return resultado;
}
// cálculo del número de catalan usando el coeficiente binomial
unsigned long long int numeroCatalan(int n)
{
unsigned long long int coef = coeficienteBinomial(2 * n, n);
return coef / (n + 1);
}
La fórmula usada en la función coeficienteBinomial()
se deriva de la definición algebraica del Coeficiente Binomial, en la cual se establece la siguiente:
Si se tiene un conjunto con n elementos, de los cuales se van a escoger k, la elección (ordenada) puede hacerse de n * (n-1) * (n-2) * ... * (n-k+1)
maneras, ya que en el primer paso se tienen n opciones, en el segundo se tienen n-1, en el tercero n-2, y así sucesivamente, terminando en el paso k que tendrá n-k+1 opciones.
Ahora, hay que dividir el producto anterior entre el número de selecciones «equivalentes».
La fórmula es la siguiente:

¡¡Y con esto, estamos calculando el valor del coeficiente binomial C(n,k)
de forma iterativa!!
Un programa que muestra las 3 formas planteadas podría verse así:
#include <iostream>
#include <vector>
using namespace std;
unsigned long long int catalan(unsigned long long int n)
{
if (n == 0)
{
return 1;
}
else
{
return (((4 * n) - 2) * catalan(n - 1) / (n + 1));
}
}
std::vector<unsigned long long int> iterativeCatalan(const std::vector<unsigned long long int> &lista)
{
std::vector<unsigned long long int> valores;
valores.push_back((unsigned long long int)1);
for (int i = 1; i <= lista.size(); ++i)
{
unsigned long long int valor = (((4 * i) - 2) * valores[i - 1] / (i + 1));
valores.push_back((unsigned long long int)valor);
}
return valores;
}
unsigned long long int coeficienteBinomial(int n, int k)
{
unsigned long long int resultado = 1;
if (k > n - k)
{
k = n - k;
}
for (int i = 0; i < k; ++i)
{
resultado *= (n - i);
resultado /= (i + 1);
}
return resultado;
}
unsigned long long int numeroCatalan(int n)
{
unsigned long long int coef = coeficienteBinomial(2 * n, n);
return coef / (n + 1);
}
int main()
{
int num;
cout << "Ingrese el número de Catalan que desee calcular:" << endl;
cin >> num;
if (num < 1)
{
cout << "El valor de Catalan para 0 es: " << 1 << endl;
return 0;
}
// RECURSIVO
unsigned long long int valor = catalan((unsigned long long int)num);
cout << "El valor de Catalan calculado de forma recursiva para " << num << " es: " << valor << endl;
// ITERATIVO
std::vector<unsigned long long int> lista(num);
std::vector<unsigned long long int> numeros = iterativeCatalan(lista);
cout << "El valor de Catalan calculado de forma iterativa para " << num << " es: " << numeros[num] << endl;
// BINOMIAL
unsigned long long int vBinomial = numeroCatalan(num);
cout << "El valor de Catalan calculado para " << num << " usando coeficiente binomial es: " << vBinomial << endl;
return 0;
}
Espero que esto aporte otra forma de resolver el problema.