感谢支持
我们一直在努力

百度面试题—疯子上飞机

题目的描述是:有100个人上飞机,本应该按照各自的座位1-100号坐下,但其中有一个是疯子

疯子的行为是:随机选择一个座位坐下。

而正常人的行为是: 尽量做自己的座位,如果自己的座位被占了,就随机选一个座位。

问题是:最后一个人坐在自己的位置的概率是多大。

分析:
这个题目里疯子登机号也是随机的,我们可以先简化问题成,假设有n个人,疯子是第一个登机的,求出最后一个人坐在自己位置的概率。

我们可以从小规模分析这个问题

n = 2, P(2)  = 0.5
n = 3
如果疯子做在自己的位置S1上,那么最后一个人肯定坐在自己的座位上 概率是 1/3

如果疯子坐在第二个人S2上,那么空余座位是 S1, S3,现在第二个人登机的时候,我们可以把他理解成疯子,他本该有的座位是S1, 所以问题变成了 n = 2的子问题

这个时候的概率是  1/3 * P(2)

如果疯子直接坐在最后一个人的位置上,那么最后一个人坐在自己座位概率就是0.

则 P(3) = 1/3 + 1/3 * P(2) + 0 = 1/2.

n = 4
类似的,如果疯子直接坐在自己的位置上,最后一个人坐在自己位置的概率 概率是 1/4
如果坐在 第二个人位置上, 最后一个人坐在自己的概率是  1/4 * P(3)
如果坐在第三个人的位置上,这个时候可能有点特殊,疯子登机后,到第三个之间还有第二个人,第二个的位置没有被占,所以他一定正常登机,这个时候当第三个人登机的时候,问题变成, 第三个人是疯子,他应该有的座位是S1,变成P(2).  所以概率是 1/4 * P(2)
如果直接坐在最后一个人座位上,那么概率是0.
计算得知 P(4) = 1/2

这样我们可以用归纳法,假设 1-n个人的时候,P(n) = 1/2
然后我们现在求 P(n+1)

根据我们上面的求法有公式
P(n+1) = 1/(n+1) + ∑i(from 2 to n)  P(n+1 – i) / (n+1) + 0 = 1/(n+1) + (n-2+1)/((n+1) 2)+ 0 = (n+1)/2(n+1) = 1/2

归纳假设成立。

所以最后的概率是 1/2.
———————————————————————————————-
不过现在还不是我们的问题,我们的问题中疯子可以任意次序登机,不过问题都可以归一为一个,因为疯子前面的所有人都会正常做自己的座位,
如果疯子第i个登机, 问题就是 P(100 – i + 1) 所有的概率都是 1/2, 所以最后总的概率也是 1/2.
———————————————————————————————-

不过面试现场没有证明出来,有点悲剧的。 sigh!

赞(0) 打赏
转载请注明出处:服务器评测 » 百度面试题—疯子上飞机
分享到: 更多 (0)

听说打赏我的人,都进福布斯排行榜啦!

支付宝扫一扫打赏

微信扫一扫打赏