简介
来自百度百科.
代码
#include
using namespace std; long long Catalan(int n) { long long a[100]; a[0]=1; for(int i=1;i<=n;i++){ a[i]=a[i-1]*(4*i-2)/(i+1); } return a[n]; } int main() { int n; while(1){ long long ans; scanf("%d",&n); ans=Catalan(n); cout<
例题
Catalan数实际上用在很多个问题上，它的应用很巧妙，并且大都是成对出现的
- 一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
f ( 2n ) =h ( n )
- n对括号正确匹配数目
给定n对括号，求括号正确配对的字符串数
f ( 2n ) =h ( n ) - 2 n 个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？
f ( 2n ) =h ( n )
- 门票找钱问题
有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？
f ( 2n ) =h ( n ) - 对于集合{1,2,3…2n}的不交叉划分的数目为多少？
我们将每个子集中较小的数用左括号代替，较大的用右括号代替，那么带入原来的1至2n的序列中就形成了合法括号问题
f ( 2n ) = h ( n ) - 一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
或者说在n*n的格子中，只在下三角行走，每次横或竖走一格，有多少中走法？
f ( 2n ) = h ( n )
- n个长方形填充一个高度为n的阶梯状图形的方法个数？
f ( n ) =h ( n )
- 在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？
f ( 2 n ) = h ( n )
- 给定节点组成二叉搜索树
给定N个节点，能构成多少种不同的二叉搜索树？
或者说有n+1个叶子的满二叉树的个数？
（能构成h（N）个）（这个公式的下标是从h(0)=1开始的）
f ( n ) = h ( n )
- 凸多边形三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f（6）=14 = h ( 4 )
即 ,f ( n ) = h ( n-2 )
- 乘积重组问题
矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
f ( n ) =h ( n – 1 )
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/218575.html原文链接：https://javaforall.net
