我要招人

去企业版

首页 > 试题广场 >

在有团购之前，大家都是现场买门票，公园的门票是5元，某天售票

[问答题]

在有团购之前，大家都是现场买门票，公园的门票是5元，某天售票处开门时没有准备零钱。假设一天来购票的依次有2N个人，其中有N个人有5元零钱，其他N个人只有10元面值的钱；假设每人只买一张票。请问任何人都不必为找零而等待的概率是多少？

推荐

jo_ryan

为了将问题简单化，将持有5元的人看成1，持有10元的人看成0，这样，只要满足：在任何0位置之前，1的数目多于0的数目，就能满足要求，则该题求解的为满足要求的排列占全部排列的比例。

1）求2n个1和0的全排列数目：C(2n,n)，即从2n个位置中选取n放置0（或者1）。

2）求取不满足要求的组合数（合法的组合数不好求）：

不满足要求的组合数的特点：总能找到一个位置K，使得0的数目比1的数目多1。那么很明显，k后面的0的数目比1的数目要少1.（为什么要找位置k？因为，我要让前面K个位置0、1排列不管怎么排列都不合法）

此后，我们关注k位置后面的排列：因为k后面的排列中，明显0比1少，那么我们可以将0和1互换（为什么要互换？首先，0、1互换后，两种排列方式的总数目是不变的，其次，互换后的排列中0比1多1个，那么不管怎么排列，都不合法），这样互换后2n个数的排列不管怎么排列都不合法（值得注意的是，互换后的组合排列数目，和互换前的是相同的，因为前面的排列不变且后面排列组合方式的数目一样。

现在来计算互换后排列的数目：互换后排列的数目中0为n+1个，1为n-1个，那么组合数就相当于从2n个位置选取n+1个位置放0，即为C（2n,n+1）

所求结果为 ( C(2n,n)-C(2n,n+1) ) / C(2n,n)

编辑于 2016-03-29 19:58:14 回复(4)

Roy

任何人不必等的情况数 Cn=2N!/(N!*N!*(N+1)) 总的情况数 T=2N!/N!*N! 不必等的概率为：Cn/T = 1/(N+1)

编辑于 2016-03-29 19:58:05 回复(1)

xxj

( C(2n,n)-C(2n,n+1) )/ C(2n,n)

发表于 2014-11-18 15:32:36 回复(0)

幻语cly

卡塔兰数，(2N)!/(N!*N!*(N+1))

发表于 2014-10-15 10:09:48 回复(1)

哈哈哈32

(N!)*(N!)/(2N!)

发表于 2014-10-12 18:07:42 回复(0)

スヲビン

我算出来的分子是n*(n-1)/2+1，分母是C(2n,n)，不知对不对，求解释。

发表于 2015-09-11 22:14:54 回复(0)

幻影迷风

<div> 满足题意的排队次数  C(N,2N)-C(N-1，2N) </div> <div> 总共的排队次数  C(N，2N) </div> <div> 二者相除得概率 </div>

发表于 2015-09-11 20:11:37 回复(0)

CloudCastle

<div> 卡特兰数<br /> 在不考虑人的区别的情况下排队情况为C(2n,n)/(n+1);<br /> 考虑到N个人两两交换产生的情况则为 C(2n,n)*n!*n!/(n+1) </div>

发表于 2015-08-18 10:50:47 回复(0)

爱尔兰咖啡

<div> public class Demo { </div> <div> <span> </span>public static float arr(){ </div> <div> <span> </span>//2n个人，n个10元 </div> <div> <span> </span>int n=10; </div> <div> <span> </span>int d=0; </div> <div> <span> </span>for(int i=0;i<n;i++){ </div> <div> <span> </span> </div> <div> <span> </span>for (int j = 0; j < n; j++) { </div> <div> <span> </span>if(i<=j){ </div> <div> <span> </span>d++; </div> <div> <span> </span>} </div> <div> <span> </span>} </div> <div> <span> </span>} </div> <div> <span> </span> </div> <div> <span> </span>int sum=1; </div> <div> <span> </span>for (int i = 1; i <2n; i++) { </div> <div> <span> </span>sum=sum*i; </div> <div> <span> </span> </div> <div> <span> </span>} </div> <div> <br /> </div> <div> <span> </span> </div> <div> <span> </span> </div> <div> <span> </span> </div> <div> <span> </span>return d/sum; </div> <div> <span> </span> </div> <div> <span> </span>} </div> <div> <span> </span> </div> <div> <span> </span>public static void main(String[] args) { </div> <div> <span> </span>System.out.printf(arr()); </div> <div> <span> </span>} </div> <div> } </div>

发表于 2015-08-16 20:22:13 回复(0)

.......1

( C(2n,n)-C(2n,n+1) )/ C(2n,n)

发表于 2015-05-05 13:52:41 回复(0)

1 - ( c(1,n) * a(2n-1,2n-1) ) / a(2n,2n) ?

发表于 2015-01-22 22:03:23 回复(0)

此刻_分享

1/2^N/2

发表于 2014-11-29 13:09:05 回复(0)

提交观点

问题信息

C++工程师美团智力题 2013 Java工程师

来自：美团2013研发笔试卷

上传者：缘定寞尘

难度：

12条回答 85收藏 11527浏览

在有团购之前，大家都是现场买门票，公园的门票是5元，某天售票

问题信息

热门推荐

相关试题