问:有多少种排队方法使得每当一个拥有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)!} \)。
考考好友
默认不带谜底。链接卡片仍是这道题的网页简介。
更多逻辑推理
新年联欢会上,同学们一致要求教数学的王老师出一
新年联欢会上,同学们一致要求教数学的王老师出一个节目。王老师微笑着走到讲台前说:“我给你们表演一个 数字 魔术吧!”说完,王老师拿出一叠纸条,发给每人一张,并神秘地说:“由于我教你们数学,所以你们脑子里的数也听我的话。不信,你们每人独立地在纸条上写上任意4个自然数(不重复写),我保证能从你们写的4个数中,找出两个数,它们的差能被3整除。” 王老师的话音一落,同学们就活跃起来。有的同学还说:“我写的数最调皮,就不听王老师的话。”不一会儿,同学们都把数写好了,但是当同学们一个个念起自己写的4个数时,奇怪的事果真发生了。同学们写的数还真听王老师的话,竟没有一个同学写的数例外,都让王老师找出了差能被3整除的两个数。 同学们,你们知道王老师 数字 小魔术的秘密吗?
4 , 9 , 1 , 4 , 3 , 40,
4 , 9 , 1 , 4 , 3 , 40,( ) 括号里面是什么? A.81 B.80 C.121 D.120
1,3,3,5,7,9,13,15( ),(
1,3,3,5,7,9,13,15( ),( ) A:19,21;B:19,23;C:21,23;D:27,30;