Рассчитать n-е каталонское число

Question

Я написал код для вычисления N-го каталонского номера. Однако он не возвращает правильный результат при N = 20 и далее. Результаты, когда N < 20 верны, поэтому я не уверен, что не так.

Итак, когда N = 20, его предполагается вернуть 6564120420, но он возвращает 2269153124 для меня.

Может кто-нибудь указать мне в правильном направлении?

#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

Вы превышаете максимальный размер этих типов переменных, которые вы можете хранить.

Тип long long - ваш лучший выбор.

Вы можете посмотреть здесь на то, что максимальные значения для различных типов целых чисел являются: http://www.cplusplus.com/reference/climits/

Answer 2

использование «без знака долго долго» вместо «без знака 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; 
}