http://www.cppblog.com/flyinghearts/archive/2013/09/18/123545.html
现在有一班飞机将要起飞，乘客们正准备按机票号码（1, 2, 3, …N）依次排队登机。突然来了一只大猩猩（对，他叫金刚）。他也有飞机票，但是他插队第一个登上了飞机，然后随意地选了一个座位坐下了。根据社会的和谐程度，其他的乘客有两种反应：
1.乘客们都义愤填膺，“既然金刚同志不遵守规定，为什么我要遵守？”他们也随意地找位置坐下，并且坚决不让座给其他乘客。
2.乘客们虽然感到愤怒，但还是以“和谐”为重，如果自己的位置没有被占领，就赶紧坐下，如果自己的位置已经被别人（或者金刚同志）占了，就随机地选择另一个位置坐下，并开始闭目养神，不再挪动位置。
那么，在这两种情况下，第i个乘客（除去金刚同志之外）坐到自己原机票位置的概率分别是多少？
（一）先看第一问，我认为作者总结的公式太抽象了，至少能看懂那个公式的人不多。
遇到这样的问题，就是枚举，猜出公式，然后数学归纳法。
假设N=3，即1、2、3。
先来分析第一个人的概率：
如果金刚占了1，概率1/3，那么第1个人永远没机会坐到自己座位，概率为0。
如果金刚不占1（占了2或3）——概率2/3，这种情况下，第1个人可以在1和另一个座位（2或3）中进行选择，概率1/2，即P=2/3 * 1/2 = 1/3。
合计：1/3——这是第一个人坐到自己座位的概率。
再来分析第2个人的概率：
果金刚占了2，概率1/3，那么第2个人永远没机会坐到自己座位，概率为0。
如果金刚不占2（占了1或3），——概率2/3，这种情况下，我们要看第1个人，分2种情况：
第1个人占2的概率为1/2（因为还剩2个位子），那么第2个人永远没机会坐到自己座位，即P=0
第1个人不占2的概率也是1/2，那么最后一个位子肯定是2，概率为1。则P=2/3*1/2 * 1=1/3
合计：1/3
第3个人的概率就不要算了，因为没有位子了（N+1个人，N个位子，最后一个人肯定没位子）。
观察得到结论：对于第i个人，我们先计算出金刚、以及第1个人、第2个人……第（i-1）个人——她们不占第i个位置的概率，分别是(N-1)/N、(N-2)/(N-1)、（N-3）/(N-2)直到(N-i)/(N-i+1)，然后计算出第i个人在剩余的N-i个位子中占到第i个位子的概率，也就是1/(N-i)，把以上这些概率相乘，乘积为1/N，这就是最后的结果。
当然，当i=N的时候，概率永远为0，因为最后一名没有位子选了。
http://hi.baidu.com/maxint/item/209b9b2cea491e9db6326342
http://blog.csdn.net/huangwwu11/article/details/19901769
现在有一班飞机将要起飞，乘客们正准备按机票号码（1, 2, 3, …N）依次排队登机。突然来了一只大猩猩（对，他叫金刚）。他也有飞机票，但是他插队第一个登上了飞机，然后随意地选了一个座位坐下了。根据社会的和谐程度，其他的乘客有两种反应：
1.乘客们都义愤填膺，“既然金刚同志不遵守规定，为什么我要遵守？”他们也随意地找位置坐下，并且坚决不让座给其他乘客。
2.乘客们虽然感到愤怒，但还是以“和谐”为重，如果自己的位置没有被占领，就赶紧坐下，如果自己的位置已经被别人（或者金刚同志）占了，就随机地选择另一个位置坐下，并开始闭目养神，不再挪动位置。
那么，在这两种情况下，第i个乘客（除去金刚同志之外）坐到自己原机票位置的概率分别是多少？
（一）先看第一问，我认为作者总结的公式太抽象了，至少能看懂那个公式的人不多。
遇到这样的问题，就是枚举，猜出公式，然后数学归纳法。
假设N=3，即1、2、3。
先来分析第一个人的概率：
如果金刚占了1，概率1/3，那么第1个人永远没机会坐到自己座位，概率为0。
如果金刚不占1（占了2或3）——概率2/3，这种情况下，第1个人可以在1和另一个座位（2或3）中进行选择，概率1/2，即P=2/3 * 1/2 = 1/3。
合计：1/3——这是第一个人坐到自己座位的概率。
再来分析第2个人的概率：
果金刚占了2，概率1/3，那么第2个人永远没机会坐到自己座位，概率为0。
如果金刚不占2（占了1或3），——概率2/3，这种情况下，我们要看第1个人，分2种情况：
第1个人占2的概率为1/2（因为还剩2个位子），那么第2个人永远没机会坐到自己座位，即P=0
第1个人不占2的概率也是1/2，那么最后一个位子肯定是2，概率为1。则P=2/3*1/2 * 1=1/3
合计：1/3
第3个人的概率就不要算了，因为没有位子了（N+1个人，N个位子，最后一个人肯定没位子）。
观察得到结论：对于第i个人，我们先计算出金刚、以及第1个人、第2个人……第（i-1）个人——她们不占第i个位置的概率，分别是(N-1)/N、(N-2)/(N-1)、（N-3）/(N-2)直到(N-i)/(N-i+1)，然后计算出第i个人在剩余的N-i个位子中占到第i个位子的概率，也就是1/(N-i)，把以上这些概率相乘，乘积为1/N，这就是最后的结果。
当然，当i=N的时候，概率永远为0，因为最后一名没有位子选了。
http://hi.baidu.com/maxint/item/209b9b2cea491e9db6326342
第二题：用 F(i, n) 表示当座位总数为n时，第 i 个乘客坐到自己原位置的概率。根据全概率公式，得
其中 P(K=j) 表示金刚坐在位置 j 上，P(i | K=j) 是条件概率，表示当金刚坐在位置 j 上时，第 i 个乘客坐到自己原位置的概率。显然 P(K=j)=1/n，现在来分析 P(i | K=j)。
- 金刚若挑自己的座位或选的座位在第i个座位后（即 i < j），则第 i 个乘客肯定能坐到原来的座位。此时 P(i │ K=j) = 1；
- 金刚若挑选的座位在第 i 个座位前，（即 i > j），则第j个乘客除非坐到金刚的座位，不然就会抢其他人的座位，因为他的行为和金刚相似，可以将他当做金刚处理。去除前 j 个座位，剩下的座位和乘客再按原大小排序重新从1开始编号，则先前的第 i 个乘客，其座位号变为 i-j，新的总座位数变为 n-j。所以得 P(i │ K=j) = F(i-j, n-j)。
由上分析得：
再取 n+1 和 i+1 代入上式并与原式相减得：
结果有误，请注意！从推导过程来看，最后一步的 i 需大于1，无法取到1，所以不成立。重新思考后发现原题目有些不解的地方：如果金刚自己的位置在 i 上，则第 i 位乘客坐在他自己的位置上的概率为0还是1，即是否认为金刚也是乘客。如果是这样分析，上面的式子就要做调整了。如金刚不算乘客，F(2,2)=1/4，而不是书上说的1/2
http://www.cnblogs.com/Jax/archive/2009/11/26/1611603.html
（二）再看第2问：
话说，这个答案是错的。
仍然按照刚才的思路进行枚举：
最简单的情况，令N=2，就是说，只有2个元素：1和2。
我们先看i=1的情形，也就是第一个乘客的概率
如果金刚选择1坐下，那么第一个乘客永远没机会，为0。
如果金刚选择2坐下，概率1/2，那么只剩下第一个位置为第一个乘客，P=1/2 * 1 = 1/2。
合计：f(1) = 1/2。
我们再看i=2的情形
还是那句话，最后一个人概率永远为0。
但是，按照作者给出的公式：这两个值分别是f(1)=2/3和f(2) = 1/2。
所以，我猜测，这个公式应该是F(i) = f(i) = (N-i)/(N-i+1)。很奇怪邹欣为什么没写几个TestCase来试试。
心里还是没底，毕竟作者是微软的，于是我分别测试了N=3和N=4情况下，i为2和3的情形。
比如说N=4，i=2
我发现，当金刚占了第1个位置，那么，第1个人不占2的概率是2/3（因为还剩下3个数），此时第2个人肯定可以占2。f(i) = 2/3
比如说N=5，i=3：
当金刚占了第1个位置，那么，接下来分只考虑第一个人不占3的两种情况：
第一个人占2的概率是1/4，那么第2个人不占3的概率是2/3，则第3个人肯定占3。
第1个人不占2也不占3的概率是1/2，此时第2个人肯定占2，第3个人肯定占3。
计：1/4 * 2/3 + 1/2 = 2/3
当金刚占了第2个位置，那么，第一个人肯定占1，第2个人不占3的概率是2/3，此时第3个人肯定可以占3。
合计2/3
将N和i（这里i>n）推而广之：
当金刚占了第n个位置，那么不计第n-1个人以前的乘客，因为他们肯定能做到自己的位置。那么现在，还有第n个乘客，以及剩下的N-n个乘客（从第n+1到第N个）。
于是问题退化为：第n个乘客化身为金刚，剩下的（N-n）个乘客按顺序登机，新的金刚插队第一个登机，随意在第n+1到第N个这（N-n）个位置中坐下……
退化题目所得到的结果F(n)和原题目的结果f(n)是一样的（这里要说清楚，一定要使用数学归纳法）。
所以，我相信，经过若干次退化后，因为n<i<N，所以n会先逼近i，也就是说，这个极限是，金刚占了第i-1个位置，然后第i-1个人不占i的可能性是（N-i）/（N-i+1），这个就是我们要计算的f(i)。
综上所述：f(i) = （N-i）/（N-i+1）。
然后进行计算，得到F(n)=（N-i）/（N-i+1）。这才是正确答案。
对问题二，答案和金刚的原来座位编号有关。不妨先去除金刚的座位，将乘客（根据机票号）和剩下的座位，按原大小顺序从1开始重新编号。用F(i，n)表示在新排列中（共有n-1个乘客座位和金刚原来的座位），新的第i个乘客坐在其原来座位的概率，则在n个座位中：
① 金刚若挑自己的座位或选的座位在第i个座位后（共有n-i个座位满足这个条件），则第i个乘客肯定能坐到原来的座位；
② 金刚若挑选的座位在第i个座位前，不妨假设为j，则第j个乘客除非坐到金刚的座位，不然就会抢其他人的座位，因为他的行为和金刚相似，可以将他当做金刚处理。去除前j个座位，剩下的座位和乘客再按原大小排序重新从1开始编号，则先前的第i个乘客，其座位号变为i-j，新的总座位数变为n-j。因而可得公式：
用 G(i, n)表示原排列中，第i个乘客坐到自己座位的概率，假设金刚的座位编号为j。
若 i<j 则 G(i,n)=F(i,n)= (n-i)/(n+1-i)。
若 i>j 则 G(i,n)=F(i-1,n)= (n+1-i)/(n+2-i) 。
类似题：
“约瑟芬环：n个人，编号为0到n-1，围成一圈，从编号为0的开始，从1开始报数，所有报到m的出列，下一个人从1开始继续报数。求最后一个人的编号。”
Also check http://jarfield.iteye.com/blog/1798180http://blog.csdn.net/huangwwu11/article/details/19901769
