我看我还是公布答案吧
【14】
本题可用递归算法,但时间复杂度为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)!],说起来太复杂,这里就不讲了。