首页 > 试题广场 >

电影院排队问题

[单选题]

有2n个人排队进电影院，票价是50美分。在这2n个人当中，其中n个人只有50美分，另外n个人有1美元（纸票子）。愚蠢的电影院开始卖票时1分钱也没有。
问：有多少种排队方法使得每当一个拥有1美元买票时，电影院都有50美分找钱
注：
1美元=100美分
拥有1美元的人，拥有的是纸币，没法破成2个50美分

```
(2n)!/[n!n!]
```
```
(2n)!/[n!(n+1)!]
```
```
(2n)!/[n!(n-1)!]
```
```
(2n + 1)!/[n!(n-1)!]
```

查看答案及解析

推荐

牛客-007

B。

这个是卡特兰数的经典应用。但是这个问题不是一两句话能说得清的，介绍卡特兰数的文章都用大量的篇幅讲他的原理。这里给你一个类似问题的描述，看看能不能看懂。

问题描述:
12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？
这个笔试题，很YD，因为把某个递推关系隐藏得很深。

问题分析:
我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排.
用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案.
比如000000111111就对应着
第一排：0 1 2 3 4 5
第二排：6 7 8 9 10 11
010101010101就对应着
第一排：0 2 4 6 8 10
第二排：1 3 5 7 9 11
问题转换为，这样的满足条件的01序列有多少个。
观察1的出现，我们考虑这一个出现能不能放在第二排，显然，在这个1之前出现的那些0,1对应的人
要么是在这个1左边，要么是在这个1前面。而肯定要有一个0的，在这个1前面，统计在这个1之前的0和1的个数。
也就是要求，0的个数大于1的个数。
OK，问题已经解决。
如果把0看成入栈操作，1看成出栈操作，就是说给定6个元素，合法的入栈出栈序列有多少个。
这就是catalan数,这里只是用于栈，等价地描述还有，二叉树的枚举、多边形分成三角形的个数、圆括弧插入公式中的方法数，其通项是c(2n, n)/(n+1)。

在<<计算机程序设计艺术>>，第三版，Donald E.Knuth著，苏运霖译，第一卷，508页，给出了证明:
问题大意是用S表示入栈，X表示出栈，那么合法的序列有多少个(S的个数为n)
显然有c(2n, n)个含S，X各n个的序列，剩下的是计算不允许的序列数(它包含正确个数的S和X，但是违背其它条件)。
在任何不允许的序列中，定出使得X的个数超过S的个数的第一个X的位置。然后在导致并包括这个X的部分序列中，以S代替所有的X并以X代表所有的S。结果是一个有(n+1)个S和(n-1)个X的序列。反过来，对一垢一种类型的每个序列，我们都能逆转这个过程，而且找出导致它的前一种类型的不允许序列。例如XXSXSSSXXSSS必然来自SSXSXXXXXSSS。这个对应说明，不允许的序列的个数是c(2n, n-1)，因此an = c(2n, n) - c(2n, n-1)。

然后回到本问题，排队买票的每个人都是不同的，n个人有1美元，n个人有50美分，最后结果在乘以A（n,n）*A(n,n),即为“[c(2n, n) - c(2n, n-1)]*A（n,n）*A(n,n)”化简为选项B

编辑于 2015-02-02 22:04:48 回复(2)

247077346@qq.com

可以用排除法，假设N=2.代入

发表于 2015-04-18 14:14:46 回复(5)

只为一次疯狂ING

n =1 就选中了正确答案

编辑于 2015-08-25 10:14:43 回复(4)

鲸池

使用排除法，首先全部情况有：（2n）!

考虑不符合的情况为：对于第k个1美元的人，其前面若少于k个50美分的则电影院无法找零。

假设：若前k个排好（k! 种）时至多有(（k-1）！种)不符合情况。(k!)(k-1)!

最后，是这2n个人混排而不是1向上述假设的一样是n个1美元的排好然后排50美分的，因此这里进行排除时应该用的是除法而不是减法。结果即为：(2n)! / [ n! (n-1)!]

发表于 2018-07-04 23:18:40 回复(0)

牛客333892576号

N=2的时候，假设A,B有50美分，C,D有100美分，有八种:

ABCD

ABDC

BACD

BADC

ACBD

ADBC

BCAD

BDAC

这个题目没问题么？？？

发表于 2020-03-30 01:28:26 回复(2)

oOElevenOo

这个题有问题，在考虑每个人都是不同的情况也就是说A1A2B1B2和A2A1B1B2是不同的可行解的情况下，正确答案应该是2n!*n!/(n+1)!。在原答案上需要考虑A和B两类人群的排列问题，再乘两个A(n,n)

发表于 2020-04-10 17:40:13 回复(0)

谁说工作了就不要刷题

get到了一招，居然有特殊法，直接带入一个值，看选项就好了。哈哈

发表于 2017-09-07 11:04:15 回复(0)

jack_kuo

本题可用递归算法，但时间复杂度为2的n次方，也可以用动态规划法，时间复杂度为n的平方，实现起来相对要简单得多，但最方便的就是直接运用公式：排队的种数=(2n)!/[n!(n+1)!]。

如果不考虑电影院能否找钱，那么一共有(2n)!/[n!n!]种排队方法（即从2n个人中取出n个人的组合数），对于每一种排队方法，如果他会导致电影院无法找钱，则称为不合格的，这种的排队方法有(2n)!/[(n-1)!(n+1)!]（从2n个人中取出n-1个人的组合数）种，所以合格的排队种数就是(2n)!/[n!n!]- (2n)!/[(n-1)!(n+1)!] =(2n)!/[n!(n+1)!]。至于为什么不合格数是(2n)!/[(n-1)!(n+1)!]，说起来太复杂，这里就不讲了。

发表于 2021-04-24 17:05:55 回复(0)

coder_zhliu

https://blog.csdn.net/weixin_45611266/article/details/101374349

发表于 2021-01-04 21:52:29 回复(0)

UpUpLuo

不会做的时候，带数。

if n == 1, result = 1 --> B

发表于 2020-04-11 18:37:32 回复(0)

棉花汤

参考博客：http://blog.csdn.net/jiejinquanil/article/details/52153045

发表于 2016-09-04 18:10:32 回复(0)

dangle

mark

发表于 2015-08-17 18:14:52 回复(0)

菩提旭光

最最简单的方法，假设法：

1.假设有4个人。那么n=2，此时有

A。6

B。2

C。12

D。60.

很显然，如果4个人。模拟一下。逆推一下。

1.最后一个是50美分，前面是1美元(1)或50美分(1)。只有这两种情况。

发表于 2015-08-13 07:32:14 回复(0)

叫我小丑就好

n*n!*n!

发表于 2015-03-18 13:56:24 回复(0)

提交观点

问题信息

百度

来自：算法工程师能力评估

上传者：小海豹

难度：

14条回答 1323收藏 13071浏览

电影院排队问题

问题信息

热门推荐

相关试题