首页 > 代码库 > 组合数学--卡特兰数-持续更新
组合数学--卡特兰数-持续更新
参考资料: 基本介绍和各种分类 http://www.cnblogs.com/topW2W/p/5410875.html
另类递归式：
h(n)=h(n-1)*(4*n-2)/(n+1); (从n开始,更常用)
前几个卡特兰数：规定C0＝1，而
分类 : 括号,栈,矩阵乘法, 凸多边形划分,二叉搜索树构造 步数上下,找零,
C1＝1，C2＝2，C3＝5，C4＝14，C5＝42，
C6＝132，C7＝429，C8＝1430，C9＝4862，C10＝16796，
C11＝58786，C12＝208012，C13＝742900，C14＝2674440，C15＝9694845基础:
poj 2084 -----------
1 //卡特兰数 2 #include<cstdio> 3 #include<cstring> 4 #define MAX 10000 5 #define BASE 10 //十进制下的大数乘法. 6 7 using namespace std; 8 9 int Array[201][MAX];10 11 void Multiply(int A[],int n,int num)//大数乘法 A[]为第一个数(以数组的形式存储.),n为最大位数,num为要乘的数字.12 {13 int i;14 int sum=0;15 for(i=n-1;i>=0;i--)16 {17 sum+=num*A[i];18 A[i]=sum%BASE;19 sum/=BASE;20 }21 }22 23 void Divide(int A[],int n,int num)//大数除法24 {25 int i;26 int div=0;27 for(i=0;i<n;i++)28 {29 div=div*BASE+A[i];30 A[i]=div/num;31 div%=num;32 }33 }34 35 int main(int argc,char *argv[])36 {37 38 //freopen("in.txt","r",stdin);39 int i;40 int n;41 memset(Array[1],0,MAX*sizeof(int));42 for(i=2,Array[1][MAX-1]=1;i<201;i++)//高坐标存放大数低位43 {44 memcpy(Array[i],Array[i-1],MAX*sizeof(int));//h[i]=h[i-1];45 Multiply(Array[i],MAX,4*i-2); //h[i]*=(4i-2);46 Divide(Array[i],MAX,i+1); //h[i]/=(i+1)47 }48 while(scanf("%d",&n)!=EOF&&n!=-1)49 {50 for(i=0;i<MAX;i++)51 {52 if(Array[n][i]!=0)53 break;54 }55 printf("%d",Array[n][i]);// 输出第一个非零的数56 i++;57 for(;i<MAX;i++)58 printf("%d",Array[n][i]);59 printf("\n");60 }61 return 0;62 }
hdu 4165 pills-----------
1 //卡特兰数 2 #include<cstdio> 3 #include<cstring> 4 #define MAX 10000 5 #define BASE 10 //十进制下的大数乘法. 6 7 using namespace std; 8 9 int Array[201][MAX];10 11 void Multiply(int A[],int n,int num)//大数乘法 A[]为第一个数(以数组的形式存储.),n为最大位数,num为要乘的数字.12 {13 int i;14 int sum=0;15 for(i=n-1;i>=0;i--)16 {17 sum+=num*A[i];18 A[i]=sum%BASE;19 sum/=BASE;20 }21 }22 23 void Divide(int A[],int n,int num)//大数除法24 {25 int i;26 int div=0;27 for(i=0;i<n;i++)28 {29 div=div*BASE+A[i];30 A[i]=div/num;31 div%=num;32 }33 }34 35 int main(int argc,char *argv[])36 {37 38 // freopen("in.txt","r",stdin);39 int i;40 int n;41 memset(Array[1],0,MAX*sizeof(int));42 for(i=2,Array[1][MAX-1]=1;i<201;i++)//高坐标存放大数低位43 {44 memcpy(Array[i],Array[i-1],MAX*sizeof(int));//h[i]=h[i-1];45 Multiply(Array[i],MAX,4*i-2); //h[i]*=(4i-2);46 Divide(Array[i],MAX,i+1); //h[i]/=(i+1)47 }48 while(scanf("%d",&n)!=EOF&&n)49 {50 for(i=0;i<MAX;i++)51 {52 if(Array[n][i]!=0)53 break;54 }55 printf("%d",Array[n][i]);// 输出第一个非零的数56 i++;57 for(;i<MAX;i++)58 printf("%d",Array[n][i]);59 printf("\n");60 }61 return 0;62 }
hdu 1023----------
1 //卡特兰数 2 #include<cstdio> 3 #include<cstring> 4 #define MAX 10000 5 #define BASE 10 //十进制下的大数乘法. 6 7 using namespace std; 8 9 int Array[201][MAX];10 11 void Multiply(int A[],int n,int num)//大数乘法 A[]为第一个数(以数组的形式存储.),n为最大位数,num为要乘的数字.12 {13 int i;14 int sum=0;15 for(i=n-1;i>=0;i--)16 {17 sum+=num*A[i];18 A[i]=sum%BASE;19 sum/=BASE;20 }21 }22 23 void Divide(int A[],int n,int num)//大数除法24 {25 int i;26 int div=0;27 for(i=0;i<n;i++)28 {29 div=div*BASE+A[i];30 A[i]=div/num;31 div%=num;32 }33 }34 35 int main(int argc,char *argv[])36 {37 38 //freopen("in.txt","r",stdin);39 int i;40 int n;41 memset(Array[1],0,MAX*sizeof(int));42 for(i=2,Array[1][MAX-1]=1;i<201;i++)//高坐标存放大数低位43 {44 memcpy(Array[i],Array[i-1],MAX*sizeof(int));//h[i]=h[i-1];45 Multiply(Array[i],MAX,4*i-2); //h[i]*=(4i-2);46 Divide(Array[i],MAX,i+1); //h[i]/=(i+1)47 }48 while(scanf("%d",&n)!=EOF)49 {50 for(i=0;i<MAX;i++)51 {52 if(Array[n][i]!=0)53 break;54 }55 printf("%d",Array[n][i]);// 输出第一个非零的数56 i++;57 for(;i<MAX;i++)58 printf("%d",Array[n][i]);59 printf("\n");60 }61 return 0;62 }
拓展:
uva 1478
未解决
这里有一本书介绍了66个相异的可由卡塔兰数表达的组合结构。 http://www-math.mit.edu/~rstan/ec/catadd.pdf (英文PDF)
补充训练题单: http://blog.csdn.net/wcr1996/article/details/46581343
组合数学--卡特兰数-持续更新
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。