卡特兰数源于组合数学，ACM中比较具体的使用例子有，1括号匹配的种数。2在栈中的自然数出栈的种数。3求多边形内三角形的个数。4，n个数围城圆圈，找不相交线段的个数。5给定n个数，求组成二叉树的种数……
此题就是第4个样例，是裸卡特兰数，但是这里牵扯的大数，可以使用java的大数类解决，但是我这里使用高精度乘法和除法模拟的（主要是java不会）。
此处的递推式为H【1】 = 1；H【n】 = H【n-1】*（4*n-2）/（n+1）{n>=2}；代码如下：
需要注意输出的形式，我这里的进制是1000，还可以更大，根据需求吧。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define jz 10000
int a[][];
void chengfa(int k,int num){
int jw = ;
for(int i = ;i >= ;i--){
jw += a[k-][i] * num;
a[k][i] = jw % jz;
jw /= jz;
}
}
void chufa(int k,int num){
int div = ;
for(int i = ;i <= ;i++){
div = div*jz + a[k][i];
a[k][i] = div / num;
div %= num;
}
}
void init(){
memset(a,,sizeof(a));
a[][] = ;
int num;
for(int i = ;i <= ;i++){
num = (*i-);
chengfa(i,num);
num = i+;
chufa(i,num);
}
}
int main()
{
init();
int n;
while(~scanf("%d",&n)){
if(n==-) break;
int pos = -;
for(int i = ;i <= ;i++){
if(a[n][i]){
pos = i;
break;
}
}
printf("%d",a[n][pos]);
for(int i = pos+;i <= ;i++){
printf("%04d",a[n][i]);
}
puts("");
}
return ;
}