卡特兰数 - 编程论坛

rjsp2017-09-14 11:49

首先要告诉别人什么是“卡特兰数”，比如：
    卡特兰数公式：
    h(0) = 1
    h(n) = h(n-1)*(4*n-2)/(n+1);
    前几项分别是：
    h(0) = 1
    h(1) = 1
    h(2) = 2
    h(3) = 5
    h(4) = 14
    h(5) = 42
    32bits所能表示的最大结果是：h(19) = 1767263190
    64bits所能表示的最大结果是：h(36) = 11959798385860453492

其次，代码要排版，比如：
    if(k==0||k==1){
    cout<<1;
    return 0;}
    改为
    if(k==0||k==1) {
        cout<<1;
        return 0;
    }
    其它的就不一一细说了

去除编译错误和警告，比如：
    h(k) 这句报错：conversion from 'long long' to 'int', possible loss of data
    要么都改为 int，要么都改为 long long

要描述一下你想解决的问题，比如：
    输入2，期待输出2，实际报错：变量b未初始化即使用
    输入4，期待输出14，实际输出8

现在，回正题，根据公式，很简单地就写出代码：

程序代码：

unsigned long long h( unsigned n )
{
    unsigned long long r = 1;
    for( unsigned i=1; i<=n; ++i )
        r = r*(4*i-2)/(i+1);
    return r;
}

#include <iostream>
using namespace std;

int main( void )
{
    unsigned n;
    cin >> n;
    cout << h(n) << endl;
}

但这个代码差在 r = r*(4*i-2)/(i+1) 这一步，r*(4*i-2)中间值太大容易溢出。通过实际计算，在h(34)时就溢出了。
理论上能计算到h(36)，但实际只能计算到h(33)，这是个bug，如果是学校考试，还能打个及格；放在商业公司的话，会被老板拿刀砍死。
因此最终代码为：

程序代码：

unsigned long long gcd( unsigned long long a, unsigned long long b )
{
    while( b != 0 )
    {
        unsigned long long t = a;
        a = b;
        b = t%b;
    }
    return a;
}

unsigned long long AmBdC( unsigned long long a, unsigned long long b, unsigned long long c )
{
    unsigned long long t = gcd( a, c );
    a /= t;
    c /= t;

    t = gcd( b, c );
    b /= t;
    c /= t;

    return a*b/c;
}

#include <cassert>

unsigned long long h( unsigned n )
{
    assert( n <= 36 );
    unsigned long long r = 1;
    for( unsigned i=1; i<=n; ++i )
        r = AmBdC( r, 4*i-2, i+1 );
    return r;
}

#include <iostream>
using namespace std;

int main( void )
{
    unsigned n;
    cin >> n;
    cout << h(n) << endl;
}