服务器评测
题目的描述是：有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！
