百度面试题---疯子上飞机

题目的描述是：有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！百度面试题 --- 锦标赛排序百度面试题目总结相关资讯互联网百度百度面试题

30亿网民坐稳啦！互联网之门将要换（今 06:51）
互联网迎来“独立日”？（03月21日）
互联网让我们变聪明了？（11/13/2015 07:53:43）

互联网从开放走向封闭（06月20日）
全球首个互联网网页上线 25 周年（12/21/2015 13:40:02）
古巴的Netflix、Hulu和Spotify不在（09/28/2015 07:00:59）

本文评论查看全部评论（0）