卡特兰数(catalan number)
条评论卡特兰数 又称卡塔兰数,卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。
原理
令h(0)=1, h(1)=1,catalan数满足递推式:
例如:$h(2) = h(0)h(1)+h(1)h(0) = 11+11 = 2$
$h(3) = h(0)h(2)+h(1)h(1)+h(2)h(0) = 12+11+21 = 5$
另类推导式:
递推关系的解为:
递推关系的另类解为:
其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …
应用
括号化 :矩阵连乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?
出栈次序 :一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?
凸多边形三角划分 :在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数f(n)。比如当n=6时,f(6)=14。
更多应用见:https://blog.csdn.net/jiejinquanil/article/details/52153045
原始代码:
1 | __int64 catalan[40]; |
大数代码:
1 | void catalan() //求卡特兰数 |
例题
http://acm.hdu.edu.cn/showproblem.php?pid=2067
小兔的棋盘
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12397 Accepted Submission(s): 6201
Problem Description
小兔的叔叔从外面旅游回来给她带来了一个礼物,小兔高兴地跑回自己的房间,拆开一看是一个棋盘,小兔有所失望。
不过没过几天发现了棋盘的好玩之处。
从起点(0,0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点),这样的路径数有多少?
小兔想了很长时间都没想出来,现在想请你帮助小兔解决这个问题,对于你来说应该不难吧!
Input
每次输入一个数n(1<=n<=35),当n等于-1时结束输入。
Output
对于每个输入数据输出路径数,具体格式看Sample。
Sample Input
1
3
12
-1
Sample Output
1 1 2
2 3 10
3 12 416024
Author
Rabbit
Source
RPG专场练习赛
Recommend
lcy | We have carefully selected several similar problems for you: 1133 2068 1267 2069 1134
/*
题目分析:为什么这个题要用卡特兰数呢?因为它的过程可以抽象成前例的样子,
比如说先往下走,在往下走了一步的情况下,就可以往右走一步,这样向下走就等同于进栈,向右走就等同于出栈,有了卡特兰数的知识,这题就相当水了。(别忘了最后要乘2啊,因为只要满足不穿过对角线的话,先往下和先往右都可以的)
输出: 第一个数字是数据的组数,第二个数是输入的数,第三个则是路径数。
*/
1 |
|
- 本文链接:卡特兰数(catalan number)
- 发布时间:2018年05月18日 - 14:28:22
- 更新时间:2021年02月03日 - 6:56:56
- 版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!
分享