卡特兰数初步

一、什么是卡特兰数(Catalan Number)

递推式：f(n) = f(0)f(n-1) + f(1)f(n-2) + ... + f(n-2)f(1) + f(n-1)f(0)

前几项：1，2，5，14，42，132，429，1430 ...

二、能解决的实际问题

特点：一旦切开，分成两块，毫无关系

Q1

（2016·acm·shanghai·网络选拔赛）n个数围成一个圈，两两连直线，线与线不能相交，问有多少种连线方式

同：2n个人坐在圆桌旁握手，手不能交叉，问握手方案数

Q2

问n个数合法的出栈序列有多少个

Q3

多边形的三角剖分数目

 Q4

给数加括号

  Q5

走格子，只能走下三角

Q6

唱票，A从未落后于B，问唱票方式种类数（同Q5）

Q7

n个节点的二叉树个数

三、代码

// 求卡特兰数（递归写法）
// 2022-12-26 @nianjin# include <stdio.h>
int solve(int n)
{if (n == 1 || n == 0) return 1; //递归出口先写else{int ans = 0;for (int i = 0; i < n; i++) ans += solve(i)*solve(n - 1 - i);return ans;}
}
int main(void)
{int n;scanf("%d", &n);printf("%d", solve(n));return 0;
}

四、更多题目