[转]http://gpww.blog.163.com/blog/static/118268164200996103932731/
问题
《编程之美》中提到了“买票找零”问题,查阅了下资料,此问题和卡特兰数 Cn有关,其定义如下:
卡特兰数真是一个神奇的数字,很多组合问题的数量都和它有关系,例如:
- Cn= 长度为 2n的 Dyck words的数量。 Dyck words是由 n个 X和 n个 Y组成的字符串,并且从左往右数, Y的数量不超过 X,例如长度为 6的 Dyck words为:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
- Cn= n对括号正确匹配组成的字符串数,例如 3对括号能够组成:
((())) ()(()) ()()() (())() (()())
- Cn= n+1个数相乘,所有的括号方案数。例如, 4个数相乘的括号方案为:
((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
- Cn= 拥有 n+1 个叶子节点的二叉树的数量。例如 4个叶子节点的所有二叉树形态:
- Cn=n*n的方格地图中,从一个角到另外一个角,不跨越对角线的路径数,例如, 4×4方格地图中的路径有:
- Cn= n+2条边的多边形,能被分割成三角形的方案数,例如 6边型的分割方案有:
- Cn= 圆桌周围有 2n个人,他们两两握手,但没有交叉的方案数。
在《Enumerative Combinatorics》一书中,竟然提到了多达 66种组合问题和卡特兰数有关。
分析
“卡特兰数”除了可以使用公式计算,也可以采用“分级排列法”来求解。以 n对括弧的合法匹配为例,对于一个序列 (()而言,有两个左括弧,和一个右括弧,可以看成“抵消了一对括弧,还剩下一个左括弧等待抵消”,那么说明还可以在末尾增加一个右括弧,或者一个左括弧,没有左括弧剩余的时候,不能添加右括弧。
由此,问题可以理解为,总共 2n个括弧,求 1~2n级的情况,第 i 级保存所有剩余 i 个左括号的排列方案数。 1~8级的计算过程如下表:
计算过程解释如下: 1级:只能放 1个“(”; 2级:可以在一级末尾增加一个“)”或者一个“ (”
以后每级计算时,如果遇到剩余 n>0个“(”的方案,可以在末尾增加一个“ (”或者“ )”进入下一级;遇到剩余 n=0个“(”的方案,可以在末尾增加一个“ (”进入下一级。
奇数级只能包含剩余奇数个“(”的排列方案
偶数级只能包含剩余偶数个“(”的排列方案
从表中可以看出,灰色部分可以不用计算。
解法
关键代码为:
double Catalan(int n)
{
if (n == 0) return 1; for (int i = 2; i <= 2 * n; i++)
{
var m = i <= n ? i : 2 * n + 1 - i;
for (int j = (i - 1) & 1; j <= m; j += 2)
{
if (j > 0) arr[j - 1] += arr[j];
if (j < n) arr[j + 1] += arr[j];
arr[j] = 0;
}
}
return arr[0];
}
其中:
n为 Cn中的 n;
arr = new double[n + 1];//arr[i]代表有 k个括弧的时候,剩余 "("个数为 i的排列方案个数 arr[1] = 1;
讨论
算法复杂度为 = O(n^2),空间复杂度为 O(n+1)。相对于利用公式计算而言,此方法的优势在于——没有乘除法,只有加法。
分享到:
相关推荐
之前玩ACM了解的一点信息,共享一下,东西不多,希望能帮到需要的人。
介绍了卡塔兰数的定义及使用场景,针对杭电hdu上的题目给出相关解析。
Catalan number,卡特兰数又称卡塔兰数,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。 令h(0)=1,h(1)=1,catalan数满足递推式:h(n)= h(0)*h(n-1)+h...
卡特兰数(英语:Catalan number),又称卡塔兰数、明安图数,是组合数学中一种常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡特兰的名字来命名。1730年左右被蒙古族数学家明安图使用于对三角函数幂...
3.2.1 卡塔兰数的第一种表示法 第63-71页 3.2.2 卡塔兰数的第二种表示法 第71-76页 3.2.3 卡塔兰数的第三种表示法 第76-81页 3.3 无穷级数求反函数的两种表示法 第81-96页 3.3.1 “通弦求弧背法解”中无穷级数...
二进制指数运算2,二进制指数运算3,二项式系数,二项分布,二分法,卡迈克尔数,卡塔兰数,上取整,检查多边形,楚德诺夫斯基算法,考拉兹序列,组合,十进制分离,十进制转分数,十二面体,双阶乘迭代,双阶乘递归...
组合数学中有非常多的组合结构可以用卡塔兰数来计数。在Richard P. Stanley的Enumerative Combinatorics: Volume 2一书的习题中包括了66个相异的可由卡塔兰数表达的组合结构。
求出栈序列个数。卡塔兰数是组合数学中一个常出现在各种计数问题中出现的数列。
卡特兰数 catalan number 卡特兰数前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,
卡塔兰数 组合序列 整点三角形 BFS最长路径 树状数组 背包 凸包面积 高精度除法取模 完全匹配KM 字符串KMP 凸包graham算法 输出最短路径 子集 拓扑排序 欧拉函数&素数筛选 Pick定理 高精度浮点数比较 日历 15数码...
卡特兰数(Catalan Number)是组合数学中应用广泛的重要计数函数,以比利时的数学家欧仁·查理·卡塔兰(1814–1894)的名字来命名,其前几项为(从第零项开始):1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,...