计算第n个加泰罗尼亚数 [英] Calculate the nth Catalan number

问题描述

我写了一些代码来计算第N个加泰罗尼亚数。但是，当N = 20和向前时，它不返回正确的结果。当N <20的结果是正确的，所以我不知道是什么问题。

I wrote some code to calculate the Nth catalan number. However, it isn't returning the correct result when N=20 and onwards. The results when N<20 is correct though, so I'm not sure what is wrong.

所以，当N = 20时，它应该返回6564120420，但是对我来说返回2269153124。

So, when N=20, its supposed to return 6564120420, but it returns 2269153124 for me.

有人可以指向正确的方向吗？

Can someone point me in the right direction?

#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;
}

推荐答案

size这些变量类型让你存储。

You're exceeding the maximum size those variable types let you store.

long long 类型是您最好的选择。

The long long type is your best bet.

您可以看看不同类型的整数的最大值是什么： http://www.cplusplus.com/reference/climits/

You can have a look here on what the max values for different types of integers are: http://www.cplusplus.com/reference/climits/

这篇关于计算第n个加泰罗尼亚数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！