首先要告诉别人什么是“卡特兰数”,比如:
卡特兰数公式:
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;
}