Catalan数
卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰（1814–1894）命名。历史上，清代数学家明安图(1692年－1763年)在其《割圜密率捷法》最早用到“卡塔兰数”，远远早于卡塔兰。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”。卡塔兰数的一般公式为 C(2n,n)/(n+1)。
性质：
令h(0)=1,h(1)=1，卡塔兰数满足递归式：
h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2),这是n阶递推关系;
还可以化简为1阶递推关系: 如h(n)=(4n-2)/(n+1)*h(n-1) ，(n>1) h(0)=1
该递推关系的解为：h(n)=C(2n,n)/(n+1)=P(2n,n)/(n+1)!=(2n)!/(n!*(n+1)!) (n=1,2,3,...)
卡塔兰数列的前几项为 [注： n = 0, 1, 2, 3, … n]
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …
代码求解：
大数相加
//大数相加
string add(string s1,string s2)
{
if(s1.length()<s2.length())
{
string temp=s1;
s1=s2;
s2=temp;
}
int i,j;
for(i=s1.length()-,j=s2.length()-; i>=; i--,j--)
{
s1[i]=char(s1[i]+(j>=?s2[j]-'':));
if(s1[i]-''>=)
{
s1[i]=char((s1[i]-'')%+'');
if(i) s1[i-]++;
else s1=''+s1;
}
}
return s1;
}
大数相乘
//大数相乘
string mult(string a,string b)
{
int flag=,i,j,k,p,q,t,max;
char ch;
string c,ans;
p=a.size()-;
q=b.size()-;
ans="";
for(i=p; i>=; i--)
{
flag=;
c="";
for(j=i; j<p; j++) c+='';
for(j=q; j>=; j--)
{
t=(b[j]-'')*(a[i]-'')+flag;
flag=t/;
c+=(t%+'');
}
if(flag) c+=(flag+'');
for(j=,k=c.size()-; j<k; j++,k--)
{
ch=c[j];
c[j]=c[k];
c[k]=ch;
}
ans=add(ans,c);
}
return ans;
}
大数除以小数
//大数除以小数
string div(string src,int n)
{
string dest="";
int len = src.length(),i,k,t = , s = ;
bool flag = true;
for(i=,k=; i<len; i++)
{
t = s*+(src[i]-);
if(t/n> || t==)
dest += (t/n+),s = t%n,flag = false;
else
{
s = t;
if(!flag)
dest += '';
}
}
return dest;
}
求解Catalan数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include<string.h>
#include<stack>
#include<set>
#include <queue>
using namespace std;
string s[]; //大数相加
string add(string s1,string s2)
{
if(s1.length()<s2.length())
{
string temp=s1;
s1=s2;
s2=temp;
}
int i,j;
for(i=s1.length()-,j=s2.length()-; i>=; i--,j--)
{
s1[i]=char(s1[i]+(j>=?s2[j]-'':));
if(s1[i]-''>=)
{
s1[i]=char((s1[i]-'')%+'');
if(i) s1[i-]++;
else s1=''+s1;
}
}
return s1;
} //大数相乘
string mult(string a,string b)
{
int flag=,i,j,k,p,q,t,max;
char ch;
string c,ans;
p=a.size()-;
q=b.size()-;
ans="";
for(i=p; i>=; i--)
{
flag=;
c="";
for(j=i; j<p; j++) c+='';
for(j=q; j>=; j--)
{
t=(b[j]-'')*(a[i]-'')+flag;
flag=t/;
c+=(t%+'');
}
if(flag) c+=(flag+'');
for(j=,k=c.size()-; j<k; j++,k--)
{
ch=c[j];
c[j]=c[k];
c[k]=ch;
}
ans=add(ans,c);
}
return ans;
} //大数除以小数
string div(string src,int n)
{
string dest="";
int len = src.length(),i,k,t = , s = ;
bool flag = true;
for(i=,k=; i<len; i++)
{
t = s*+(src[i]-);
if(t/n> || t==)
dest += (t/n+),s = t%n,flag = false;
else
{
s = t;
if(!flag)
dest += '';
}
}
return dest;
}
int main()
{
s[]="";
for(int i=; i<; i++)
{
char s1[];
sprintf(s1,"%d",*i-);
s[i] = mult(s[i-],s1);
s[i] = div(s[i],i+);
}
int n;
while(scanf("%d",&n))
{
if(n==-) break;
cout<<s[n]<<endl;
}
return ;
}