百科 教育 动画 游戏 博览 网址 金融 搜搜 资料
触屏版

close ◇ 读取数据,请稍候 Loading...

.: Welcome to flymote.com [flymot.com] :.

网页太慢?试试: 或 [ 刷新 ]

(211073 填空/问答) 有2n个人排队进电影院,票价是50美分。在…

上一条 · * 浏览 202 *   收藏 收藏夹  ◇百科首页 ◇回上页 〖更多 趣味问答…〗 · 下一条

有2n个人排队进电影院,票价是50美分。在这2n个人当中,其中n个人只有50美分,另外n个人有1美元(纸票子)。愚蠢的电影院开始卖票时1分钱也没有。
问: 有多少种排队方法 使得 每当一个拥有1美元买票时,电影院都有50美分找钱
注: 1美元=100美分
拥有1美元的人,拥有的是纸币,没法破成2个50美分

 答案:

A. 本题可用递归算法,但时间复杂度为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)!],说起来太复杂,这里就不讲了。

 【附述】

  同类信息:
一种用舌头解不开,就用牙齿咬的解决政…为什么冬天大雁要飞到南方去?
哪个连的人员比一般连队的人员要多得多?什么时候太阳会从西边升起?
什么情况下3+1=5?有一头头朝北的牛,它向右转原地转三圈…
3个人3天用3桶水,9个人9天用几桶水?一家业务繁忙的医院却没有病床,为什么?

【最近的搜索】:

上一条 · 收藏   收藏夹 ◇回上页 〖更多 趣味问答…〗 · 下一条

百科知道 首页 百科知道 首页
CopyRight(c) 2007 - 2017 All Rights Reserved  【赣ICP备12001042号】
触屏版 | Archiver 20191013 19:55 | 简介 | 帮助 | 留言 | 关于 | 360网站安全检测平台