大海老师的算法世界
影院找钱
2n个人排队进电影院，票价是50元。在这2n个人当中，其中n个人只有50元，另外n个人只有100元面钞。愚蠢的电影院开始卖票时1分钱也没有。问：有多少种排队方法使得每当一个拥有100元面钞的人买票时，电影院都有50元找钱？
答案：
本题可用递归算法，但时间复杂度为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)!]。
 
2024-05-18
浏览99
编程思维
登录后评论
评论
分享