卡特兰数的两种计算方法

时间:2021-07-10 18:32:06
#include <stdio.h>
#include <stdlib.h>


#define MAXN        40


long long Catalan[MAXN];


long long CatalanCalc()
{
    Catalan[0]=1;
    Catalan[1]=1;
    for(long long i = 2; i < MAXN; i++)
    {
        Catalan[i] = 0;
        for(long long j = 0; j < i; j++)
            Catalan[i] += (Catalan[j] * Catalan[i-1-j]);
    }
}


long long CatalanCalc2()
{
    Catalan[0]=1;
    Catalan[1]=1;
    for(long long i = 2; i < MAXN; i++)
    {
        Catalan[i] = Catalan[i-1] * (4 * i - 2) / (i + 1);
    }
}


int main()
{


#define FILE_IN_OUT


#ifdef FILE_IN_OUT
    freopen ("test.in","r",stdin);
    freopen ("test.out","w",stdout);
#endif


    int n;
    //CatalanCalc();
    CatalanCalc2();
    while (scanf("%d",&n)!=EOF&&printf("%lld\n",Catalan[n]));


#ifdef FILE_IN_OUT
    fclose(stdin);
    fclose(stdout);
#endif


    return 0;
}