题目中对卡特兰数的总结很不错
以下copy自题目
Catalan数列:1,1,2,5,14,42,(前面几个要背)
即 h(0)=1,h(1)=1,h(2)=2,h(3)=5...
公式:h(n)=C(n,2n)/(n+1) 注:C(3,5)表示组合数5个数选3个的方案数
递推公式:h(n)=h(n-1)*(4*n-2)/(n+1);
是不是很简单呀?下面的题也是Catalan数:
1:有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票, 剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?
2:一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?
3:在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
4:对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数?
5:一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
6:n个结点可够造多少个不同的二叉树?
7:n个不同的数依次进栈,求不同的出栈结果的种数?
8:n个+1和n个-1构成2n项 a1,a2,...,a2n 其部分和满足a1+a2+...+ak>=0(k=1,2,3,..,2n)的数列的个数等于第n个Catnlan数。
有一次某同学推不出规律,暴力了前面的数据,看着眼熟,于是~~~~知道为什么要背了吧—_—!
代码
#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 55;
ll h[MAXN];int main()
{h[0] = 1;_for(i, 1, MAXN) h[i] = h[i-1] * (4 * i - 2) / (i + 1);ll x;scanf("%lld", &x);printf("%lld\n", h[x]);return 0;
}