Catalan - 卡特兰数

问题

卡特兰数（又称卡塔兰数）是组合数学中常见的数列，在计算凸多边形面积划分和棋盘路径、以及进出栈方法数中具有很多应用。

卡特兰数 C_{n} 满足以下递推关系：

$$

f(n) = frac{1}{n + 1}(
\begin{cases}
2 \times n \
n
\end{cases}
) & 其中（n \ge 0）

$$

卡特兰数可以解决的问题：

计算n+2条边的凸多边形中划分三角形的个数
在此模型中，选取任意的两条边为基点，在剩余的n条边中，可知是
两部分的卷积公式 Cn=sum(Ci*C(n-i)) 0<i<n

计算网格中的路径方案数：
在n*n的网格中，求从左下角到右上角的路径的方案数，
要求不能穿过对角线
这个问题可以转换成第三中模型

进出栈的问题：
设有n个1和n个-1随机组合，在其中添加括号，是的每个括号中的值
都不为负数，也就是一类dyck word数的计算

dyck word数：是一个有n个X和n个Y组成的字串，且所有部分的字串
满足x的个数不小于y的个数，一下为5中情况(n=3)
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
将上述X换成左括号，Y换成右括号，Cn表示组合式算法个数C3=5.

求出 n 的卡特兰数 f(n)

解法

include

include

include

using namespace std;

void catalan(int*a,int b) //求卡特兰数
{
int i,j,len,carry,temp;
a[1][0]=b[1]=1;
len=1;
for(i=2;i<=100;i++)
{
for(j=0;j=0;j—) //除法
{
temp=carry*10+a[i][j];
a[i][j]=temp/(i+1);
carry=temp%(i+1);
}
while(!a[i][len-1]) //高位零处理
len—;
b[i]=len;
}
}

源码

import, lang:”c_cpp”

测试

import, lang:”c_cpp”