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

版权声明:本文为博主原创文章,未经博主允许不得转载。 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开始的)


求卡特兰数代码如下:

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;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能

每个AI程序员都应该知道的基础数论

-欢迎 这篇文章讨论了数论中每个程序员都应该知道的几个重要概念。本文的内容既不是对数论的入门介绍,也不是针对数论中任何特定算法的讨论,而只是想要做为数论的一篇参...

23870
来自专栏程序员互动联盟

【编程之美】票买完了,零钱哪去了?

买票找零 假设有2N个人在排队买票,其中有N个人手持50元的钞票,另外有N个人手持100元的钞票,假设开始售票时,售票处没有零钱,问这2N个人有多少种排队方式...

34770
来自专栏小樱的经验随笔

2017广东工业大学程序设计竞赛决赛 题解&源码(A,数学解方程,B,贪心博弈,C,递归,D,水,E,贪心,面试题,F,贪心,枚举,LCA,G,dp,记忆化搜索,H,思维题)

心得: 这比赛真的是不要不要的,pending了一下午,也不知道对错,直接做过去就是了,也没有管太多! Problem A: 两只老虎 Description ...

33460
来自专栏数据结构与算法

BZOJ1004: [HNOI2008]Cards(Burnside引理 背包dp)

  小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有 多少种染色方案,Sun很快就给出了答案.进一步...

10230
来自专栏HansBug's Lab

1627: [Usaco2007 Dec]穿越泥地

1627: [Usaco2007 Dec]穿越泥地 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 504  So...

27970
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第二章转向行为(下)

在上一篇里,我们学习了“自主角色”的一些基本行为:寻找(seek)、避开(flee)、到达(arrive)、追捕(pursue)、躲避(evade)、漫游(wa...

283100
来自专栏小樱的经验随笔

POJ 1741 Tree(树的点分治,入门题)

Tree Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 21357 ...

32460
来自专栏Java帮帮-微信公众号-技术文章全总结

Java案例-打印图形与π

五一国际劳动节又称国际劳动节、劳动节,是世界上大多数国家的劳动节。节日源于美国芝加哥城的工人大罢工,为纪念这次伟大的工人运动,1889年的第二国际成立大会上宣布...

32650
来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第五章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

51290
来自专栏PHP在线

PHP CodeBase: 生成N个不重复的随机数

有25幅作品拿去投票,一次投票需要选16幅,单个作品一次投票只能选择一次。前面有个程序员捅了漏子,忘了把投票入库,有200个用户产生的投票序列为空。那么你会如何...

34550

扫码关注云+社区

领取腾讯云代金券