问：有多少种排队方法使得每当一个拥有1美元买票时，电影院都有50美分找钱。
有2n个人排队进电影院，票价是50美分。在这2n个人当中，其中n个人只有50美分，另外n个人有1美元（纸票子）。愚蠢的 电影院开始卖票时1分钱也没有。问：有多少种排队方法使得每当一个拥有1美元买票时，电影院都有50美分找钱。 注：1美元=100美分，拥有1美元的人，拥有的是纸币，没法破成2个50美分
答案本题可用递归算法，但时间复杂度为2的n次方，也可以用动态规划法，时间复杂度为n的平方，实现起来相对要简单得多，但最方便的就是直接运用公式：\( 排队的种数=\frac{(2n)!}{n!(n+1)!} \)。 如果不考虑电影院能否找钱，那么一共有\( \frac{(2n)!}{n!n!} \)种排队方法（即从2n个人中取出n个人的组合数），对于每一种排队方法，如果他会导致电影院无法找钱，则称为不合格的，这种的排队方法有\( \frac{(2n)!}{(n-1)!(n+1)!} \)（从2n个人中取出n-1个人的组合数）种，所以合格的排队种数就是\( \frac{(2n)!}{n!n!}-\frac{(2n)!}{(n-1)!(n+1)!}=\frac{(2n)!}{n!(n+1)!} \)。
分享谜题
相关谜语
有几个人到诺海星访问，由一名诺海星当地的翻译陪
有几个人到诺海星访问，由一名诺海星当地的翻译陪同。这位翻译尽力向来访者描述诺海星人身体上的特点。下面列出了翻译对5 个诺海星人的描述: 1、身高为3.25 米的那个人年龄不像身高为3 米的那个人那
请问：这一天是星期几？
在非洲某地，有两个奇怪的部落，一个部落的人在星期一、星期三、星期五说谎，另一个部落的人在星期二、星期四、星期六说谎。在其他日子，两个部落的人都说实话。一天，一位探险家迷路了，无意之中来到这个地方。探险
请问这三个数是多少。
A,B两人参加猜数比赛，A被告知三个正整数的和S，B被告知三个之积P。 A对B说：如果你的数比我的数大，我就能猜出这三个数。 B说：可惜我的数比你的数小，这三个数是X,Y,Z。 请问这三个
大花猫是捕鼠能手，每天要抓到不少老鼠。但它在吃
大花猫是捕鼠能手，每天要抓到不少老鼠。但它在吃老鼠以前，先要叫老鼠列队报数。第一批吃掉报单数的；剩下的老鼠重新报数。第二批，花猫仍吃掉报单数的；第三批也是如此……最后剩下的一只老鼠可以被保留，与第二天