前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一道面试题到卡特兰数及其应用

一道面试题到卡特兰数及其应用

作者头像
大黄大黄大黄
发布2018-09-14 18:01:42
6190
发布2018-09-14 18:01:42
举报
文章被收录于专栏:机器学习从入门到成神

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/53924772

绘画展览门票每张5元,如果有2n个人排队购票,每人一张,并且其中一半人恰有5元钱,另一半人恰有10元钱,而票房无零钱可找,那么如何将这2n个人排成一列,顺次购票,使得不至于因票房无零钱可找而耽误时间,应该采用什么算法解决呢?(分支限界法)

这个是卡特兰数的经典应用。那么,我们先来看一下卡特兰数是什么东西呢?

Catalan数的定义:

令h(1)=1,Catalan数满足递归式:h(n) = h(1)h(n-1) + h(2) h(n-2) + … + h(n-1)*h(1),n>=2 该递推关系的解为:h(n) = c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)

问题描述:

12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

应用公式:c(2n, n)/(n+1)。

而c(12, 6)/7 = 12*11*10*9*8*7/(7*6*5*4*3*2) = 132

注意:c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)


应用

1、括号化

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

h(n-1)种

2、出栈次序

一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?

输出序列的总数目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)=h(n)。

类似问题:

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

3、凸多边形三角划分

在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数f(n)。比如当n=6时,f(6)=14。

f(n)=h(n-2) (n=2,3,4,……)

类似问题:

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

4、给定节点组成二叉搜索树

给定N个节点,能构成多少种不同的二叉搜索树?

(能构成h(N)个) (这个公式的下标是从h(0)=1开始的)


求卡特兰数代码如下:

代码语言:javascript
复制
void catalan() //求卡特兰数
{
    int i, j, len, carry, temp;
    a[1][0] = b[1] = 1;
    len = 1;
    for(i = 2; i <= 100; i++)
    {
        for(j = 0; j < len; j++) //乘法
        a[i][j] = a[i-1][j]*(4*(i-1)+2);
        carry = 0;
        for(j = 0; j < len; j++) //处理相乘结果
        {
            temp = a[i][j] + carry;
            a[i][j] = temp % 10;
            carry = temp / 10;
        }
        while(carry) //进位处理
        {
            a[i][len++] = carry % 10;
            carry /= 10;
        }
        carry = 0;
        for(j = len-1; j >= 0; j--) //除法
        {
            temp = carry*10 + a[i][j];
            a[i][j] = temp/(i+1);
            carry = temp%(i+1);
        }
        while(!a[i][len-1]) //高位零处理
        len --;
        b[i] = len;
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016年12月29日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 应用
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档