本文主要是介绍卡特兰数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
卡特兰数列的递推公式如下：
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)
例如:h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2
h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5
另类递推式:
h(n)=h(n-1)*(4*n-2)/(n+1);
递推关系的解为:
h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
递推关系的另类解为:
h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)
证明在百度上就可以，我主要想说的是我对卡特兰数列的理解:
卡特兰数列解决问题时的主要特征是进行两种操作，求解可行的方案数量，例如数的出入栈，分为出栈和入栈两个操作；在坐标轴上从原点向（m，n）行走，每次只能向右或者向上行走一个单位；求解决这两个问题的具体方案数量借助卡特兰数极为简便，下边给出求卡特兰数列的C语言代码：
在这里我对代码解释一下，例如问题二，求到（m，n）的方案数量就可以输入m，n直接进行解决。
#include<stdio.h>
int main()
{__int64 a[30][30]={0};int i,j,n,m;a[0][0]=1;a[1][0]=1;for(i=0;i<30;i++)for(j=0;j<=i;j++){if(j==0)a[i][j]=1;else if(j==i)a[i][j]=a[i][j-1];elsea[i][j]=a[i-1][j]+a[i][j-1];}while(1){scanf("%d%d",&n,&m);printf("%I64d\n",a[n+1][m+1]);}return 0;
}
这篇关于卡特兰数列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
