欢迎来到入门教程网!

C语言

当前位置:主页 > 软件编程 > C语言 >

深入理解卡特兰数及其应用

来源:本站原创|时间:2020-01-10|栏目:C语言|点击:

Catalan number,卡特兰数又称卡塔兰数,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。
令h(0)=1,h(1)=1,catalan数满足递推式:h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)
catalan数公式的一般是形式为:
                                                         

递推关系:

它也满足

 
这提供了一个更快速的方法来计算卡塔兰数。

卡特兰数的应用n个元素顺序入栈,出栈顺序有多少种?此问题是一个卡特兰数问题,证明过程如下:

令1表示进栈,0表示出栈,则可转化为求一个2n位、含n个1、n个0的二进制数,满足从左往右扫描到任意一位时,经过的0数不多于1数。显然含n个1、n个0的2n位二进制数共有个,下面考虑不满足要求的数目。

考虑一个含n个1、n个0的2n位二进制数,扫描到第2m+1位上时有m+1个0和m个1(容易证明一定存在这样的情况),则后面的0-1排列中必有n-m个1和n-m-1个0。将2m+2及其以后的部分0变成1、1变成0,则对应一个n+1个0和n-1个1的二进制数。

反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。
因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。 显然,不符合要求的方案数为c(2n,n+1)。

从而。证毕。

括号化问题   如,矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(h(n)种)

出栈次序问题  
1、一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
2、有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)。

将多边行划分为三角形问题  
1、将一个凸多边形区域分成三角形区域的方法数?
2、一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?
3、在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?

给顶节点组成二叉树的问题  给定N个节点,能构成多少种不同的二叉树?

一些笔试题
1、16个人按顺序去买烧饼,其中8个人每人身上只有一张5块钱,另外8个人每人身上只有一张10块钱。烧饼5块一个,开始时烧饼店老板身上没有钱。16个顾客互相不通气,每人只买一个。问这16个人共有多少种排列方法能避免找不开钱的情况出现。
h(8)=16!/(8!*9!)=1430,所以总数=h(8)*8!*8!=16!/9
2、在图书馆一共6个人在排队,3个还《面试宝典》一书,3个在借《面试宝典》一书,图书馆此时没有了面试宝典了,求他们排队的总数?
h(3)=6!/(3!*4!)=5,所以总数=h(3)*3!*3!=180

上一篇:在vs2010中,输出当前文件路径与源文件当前行号的解决方法

栏    目:C语言

下一篇:解析C++中虚析构函数的作用

本文标题:深入理解卡特兰数及其应用

本文地址:https://www.xiuzhanwang.com/a1/Cyuyan/4407.html

网页制作CMS教程网络编程软件编程脚本语言数据库服务器

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:835971066 | 邮箱:835971066#qq.com(#换成@)

Copyright © 2002-2020 脚本教程网 版权所有