1、写书评，赢取编程之美微软技术面试心得 金刚坐飞机问题 国外有一个谚语： 问：体重 800磅的大猩猩在什么地方坐? 答：它爱在哪儿坐就在哪儿坐。 这句谚语一般用来形容一些“强人”并不遵守大家公认的规则，所以要对其行为保持警 惕。 现在有一班飞机将要起飞，乘客们正准备按机票号码（1, 2, 3, N）依次排队登机。突 然来了一只大猩猩（对，他叫金刚）。他也有飞机票，但是他插队第一个登上了飞机，然后 随意地选了一个座位坐下了 1 。根据社会的和谐程度，其他的乘客有两种反应： 1. 乘客们都义愤填膺， “既然金刚同志不遵守规定， 为什么我要遵守？”他们也随意地找 位置坐下，并且坚决不让座给其他乘客。
2、2. 乘客们虽然感到愤怒，但还是以“和谐”为重，如果自己的位置没有被占领，就赶紧坐 下，如果自己的位置已经被别人（或者金刚同志）占了，就随机地选择另一个位置 坐下，并开始闭目养神，不再挪动位置。 那么，在这两种情况下，第 i 个乘客（除去金刚同志之外）坐到自己原机票位置的概率 分别是多少？ 1 金刚的口头禅是我是金刚，我怕谁？大家在旅途中可能看见过类似的事儿。 写书评，赢取编程之美微软技术面试心得 分析与解法 这两个问题之间有一处小小的区别，这个区别是如何影响最后的概率的呢？ 【问题 1 的解法】 我们可以用 F（i）来表示第 i 个乘客坐到自己原机票位置的概率。 第 i 个乘客坐到自己位置（
3、概率为 F（i），则前 i-1 个乘客都不坐在第 i 个位置（设 概率为 P （i-1） ） ， 并且在这种情况下第 i 个乘客随即选择位置的时候选择了自己的位置 （设 概率为 G（i）。 而 P（i-1）可以分解为前 i-2 个乘客都不坐在第 i 个位置的概率 P（i-2），和在前 i-2 个 乘客都不坐在第 i 个位置的条件下第 i-1 个乘客也不坐在第 i 个位置上的概率 Q（i-1）。 于是得到如下的公式（合并结果）： F（ i） = G（ i） * P（ i -1） = G（ i） * Q（ i -1） * P（ i -2） = G（ i） * Q（ i -1） Q（ 2） * P（
4、 1） 容易知道 Q（i）=（N-i）/（N- i + 1）, P（1）= （N-1）/ N, G（i）= 1/（N-i + 1） 代入公式得到，F（i）= 1/N。 【问题 2 的解法】 可以按照金刚坐的位置来分解问题，把原问题从“第 i 个乘客坐在自己位置上的概率是 多少”变为“如果金刚坐在第 n 个位置上，那么第 i 个乘客坐在自己位置上的概率是多少”（设 这个概率为 f（n）。 现在金刚坐在了 n 号位置上。如果 n=1 或 ni，那么第 i 个乘客坐在自己位置上的概率 是 1 （因为大家会尽量坐到自己的位子上， 2 号乘客将选择坐到 2 号位置上） 。 如果 n=i， 那么第 i 个
5、乘客是没希望坐到自己的位置上了（他还不至于敢和金刚 PK）。如果 1 = ， 另 1n, n+1i-1 可得： 2 1 ) ( + + = i N i N n f ，所以 则 就是第 i 个乘客坐在自己位置上的概率。 写书评，赢取编程之美微软技术面试心得 回顾 有些问题看起来规模太大而无从下手。 这时我们可以采用分而治之的方法， 这个方法有 两个核心步骤： 1. 分解问题，得到局部问题的答案。 2. 合并问题的解答。 扩展问题 在这个问题假设所有乘客是按照机票座位的次序（1，2，3，）登机的，在现实生活 中，乘客登机并没有一定的次序。如果在金刚抢先入座之后，所有乘客以随机次序登机，并 且有原来题目所描述的两种行为，那第 i 个乘客坐到自己原机票位置的概率分别是多少？
