卡特兰数:hdu-2067 小兔的棋盘&&火车出栈问题
2019-01-21 本文已影响0人
坠木
卡特兰数,一串神奇的数字,1,2,5,14......
首先了解一下卡特兰数.
卡特兰数（好像很有用的说） - Coco_T的博客 - CSDN博客
类似问题有火车进栈或是棋盘问题.题的链接如下.
首先是火车进栈,
然后还有小兔的棋盘.
代码如下.是递归球法,另外还有一个公式,an=(2n!)/(n!(n+1)!);
#include<stdio.h>
long long int we[40][40]={0};
int main()
{
int n;
int d=1;
while(scanf("%d",&n)!=EOF && n!=-1){
we[1][1]=1;
for(int i=2;i<=n+1;i++){
for(int j=1;j<=i;j++){
if(j==1)
we[i][j]=we[i-1][j];
else if(j==i)
we[i][j]=we[i][j-1];
else
we[i][j]=we[i-1][j]+we[i][j-1];
}
}
printf("%d %d %lld\n",d++,n,we[n+1][n+1]*2);
}
return 0;
}
