c++ - sucesion - termino enesimo wikipedia

Calcule el enésimo número catalán

Question

Escribí un código para calcular el N ° número catalán. Sin embargo, no devuelve el resultado correcto cuando N = 20 en adelante. Los resultados cuando N <20 es correcto, así que no estoy seguro de qué es lo que está mal.

Entonces, cuando N = 20, se supone que debe devolver 6564120420, pero me devuelve 2269153124.

¿Alguien me puede apuntar en la dirección correcta?

#include <iostream>
using namespace std;
unsigned long int countTree(unsigned int N)
{
//used to store catalan numbers
unsigned long int catalan[N+1];
//N(0)=N(1)=1
catalan[0]=catalan[1]=1;
int i,j;
for(i=2;i<=N;i++)
{
catalan[i]=0;
for(j=0;j<i;j++)
{
catalan[i]+=catalan[j]*catalan[i-j-1];
}
}
return catalan[N];
}
int main()
{
unsigned int x;
cout<<"Input N:"<<endl;
cin>>x;
unsigned long int result=countTree(x);
cout<<result<<endl;
return 0;
}

Answer 1

Está excediendo el tamaño máximo que esos tipos de variables le permiten almacenar.

El tipo long long es tu mejor apuesta.

Puede ver aquí cuáles son los valores máximos para diferentes tipos de enteros: http://www.cplusplus.com/reference/climits/

Answer 2

utilice "unsigned long long" en lugar de "unsigned int".

#include <iostream>
using namespace std;
unsigned long long countTree(unsigned int N)
{
//used to store catalan numbers
unsigned long long catalan[N+1];
catalan[0]=catalan[1]=1;
int i,j;
for(i=2;i<=N;i++)
{
catalan[i]=0;
for(j=0;j<i;j++)
catalan[i]+=catalan[j]*catalan[i-j-1];
}
return catalan[N];
}
int main()
{
unsigned int x;
cout << "Input N:" << endl;
cin >> x;
cout << countTree(x) << endl;
return 0;
}