数学智力课程:电影院排队

　　 数学智力课程:电影院排队

逻辑思维题内容：

小学趣味数学

习题：

　　有2n个人排队进电影院，票价是50美分。在这2n个人当中，其中n个人只有50美分，另外n个人有1美元(纸票子)。愚蠢的电影院开始卖票时1分钱也没有。

　　问：有多少种排队方法使得每当一个拥有1美元买票时，电影院都有50美分找钱。

　　注：

　　1美元=100美分

　　拥有1美元的人，拥有的是纸币，没法破成2个50美分。

【答案请看】

【答案】

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

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

更多相关推荐:
北大考数学智力题 :谁姓什么
智力数学校本课程纲要 小学生三年级趣味数学题（五十
六七岁智力数学题:代表什么数?