傻子坐飞机的问题

      100个人排队乘坐有100个座位的飞机，正常情况时每个都都会对号入坐，但是，第一个上飞机的是个傻子，他随机坐了一个位子，接下来的人上飞机时，如果自己座位被人坐了就会随机找个座位坐下，否则就坐自己坐位。问题：最后一个上飞机的人坐到自己座位的概率是多少？

 

问题分析：

      这道题很久以前看过，而且看到好多人争论这道题的答案，今天不知道怎么就突然想起来了。记得当时看到多数人同意的就2个答案，一个是0.5，另外一个忘记了。记得在看完这道题后我思考了好几天（也许有的人很快就能作出答案来，我还是比较笨的，呵呵），开始的时候一直没有什么好的思路。我不太喜欢暴力破解，呵呵。那几天一直想着这道题的解题思路，开始的时候在脑子里一直闪现的都是什么递归，动态规划，0-1背包等经典的题目和解法，希望能找到答案，不过还是一直都没有把他们联系上。可是脑海中还是不停的闪现着这些思路，终于有一天，让我想到了。

 

解题思路：

      上面说了一堆的废话，下面言归正传，说下本题的思路。

      其实这道题目可以归类到递归中，说到这里，可能好多人不太理解，怎么和递归扯上关系了。递归思路的关键就是一句话"傻子是可以传递的"，只要能想明白这句话，题目就迎刃而解。设n个傻子坐飞机的概率是F（n），那么题目的解就是求F（100）的值。

      首先假设有题目中的不是100个人，而是n个人，第一个上飞机的是个傻子，他坐到自己座位上的概率是1/n，这是剩下的n-1个都是正常人，他们的座位都没有被占，所以他们100%会全部坐到自己的座位，即在这种情况下最后一个坐到自己座位的概率是1/n.

      另外一种情况是这个傻子坐到了最后一个人的位置，那么剩下的人无论怎么坐最后一个人都不会坐到自己的位置，这种情况的概率是0;

      第三种情况是傻子坐到了其余n-2个人的座位上，例如他坐到了第m个人的位置（1 < m < 100，概率都是1/n），那么2---m-1号的人都会坐到自己的位置上，因为自己的位置没有人坐。而第m个人由于自己的座位被第一个傻子坐了，所以他要随即坐，这是我们可以他第m个人看做是一个傻子，因为这种情况下他的表现和傻子是一样的，因此这种情况下的概率是1/n*F（n-m+1），即把剩下的n-m+1个人看做是一个n-m+1个人规模的傻子坐飞机的问题。

 

     综上三种情况：这个问题的解就是 F（n）=1/n+0+(F(n-1)+F(n-3)+...+F(2))/n;

看到上述的递推公式出来了，那么题目也就可以解决了。可是等等，我们要求的结果是F（100），而F（100）=1/100+

(F(99)+F(98)+...+F(2))/100,如果按照这个递归公式展开，而F（99）=1/99+(F(98)+F(97)+...+F(2)/99，而且F（98），F（97）每个展开都会产生很多个函数调用，这样的话你的内存马上就有可能耗空。那么如何解决这个问题呢，难道眼睁睁的看着到手的鸭子就让它飞了。当然不行了

      如果你对算法理解稍微深点，主要是循环，也许你马上就能提出一个解决的方法。对了，就是从F（2）开始计算，依次计算F（2），F（3）。。。F（100），每次把求得的结果存到一个数组里，那么比如知道了F（2）到F（9）的值，他们依次存在一个数组f[2],f[3]...,f[9]，那么在求F（10） = 1/10+(F(9)+F(8)+...+F(2))/10的时候就不用依次递归来调用求F（9），F（8）的值了，只要依次查找数组f[2],f[3]....f[9]的值代替就好了。

      相信看到上面一步好多人已经感觉很不错了，至少内存的问题解决了，那么能不能进一步化简呢？当然能了，只要仔细观察下表达式就能发现问题所在了，每次求F（n）其实最麻烦的就是求后面括号里几项和，刚才我们用数组存储结果来表达上述的值简化了循环调用的麻烦，可是我们发现后几项的和总是从F（2）加起，一直加到F（n-1），所以我们不用每次都计算f[2]+f[3]+...+f[n-1]，主要用一个变量例如temp来保存当前的f[2]+f[3]+...f[n-1]即可，那么在计算F（n+1）的时候，我们只要在temp的基础上加上f（n）的值就可以得到f[2]+f[3]+...+f[n]即可。

     

      题目到此为止了吗？也许你说只要写个小的程序就可以很快知道结果了，可是我可以直接和你说出答案来，不用运行程序，你随便给我一个大一些的，比如1000个人坐飞机，我也可以马上告诉你答案，呵呵。你知道为什么吗？也许有的人已经猜出来了，不是我比较牛，而是答案比较特殊。答案就是1/2!

      为什么呢？学过数学归纳法吗？对了，就是用数学归纳法，对于很多的问题，如果我们已经能推出问题的表达式，但是无法证明的时候，我们很多时候用的都是数学归纳法。

     

证明过程:

      1.n=2时，傻子坐到自己位置的概率是1/2，剩下一个人坐到自己的位置，概率1/2.傻子坐到第二个人的位置的时候，最后一个人总不能坐到自己的座位，概率0.因此F（2）=1/2;

      2.假设F（2）=F（3）=。。。=F（n-1）=1/2,那么F（n）=1/n+(F(n-1)+F(n-2)+...+F(2))/n.由于F（2）=F（3）=。。。=F（n-1）=1/2，所以F（n）=1/n+(1/2+1/2+...+1/2)/n;（注：括号中共有n-2个1/2），因此可以得到F（n）=1/n+(1/2*(n-2))/n=1/2;

     3.所以F（n）=1/2 （当n >= 2时）成立

证明结束

 

题目总结：

     1.回顾下该题目，首先把这道题能够分解成很多小的问题，找到递归的思路。

     2.然后涉及到了一个将递归的程序转换成非递归的问题，这种思路我们平时解题的时候也经常根据具体条件来使用。

     3.剩下对于题目的简化就完全是观察的结果，根据题目的特殊表达式进行优化，这个是很有必要的。有的时候，好的

        优化可以大大减少计算的复杂度，提高算法的效率。

     4.最后数学归纳法也是以前证明问题常用的解法。

     

      对于这道题目，如果有的人问我程序怎么写，我觉得就是几个语句，先让对方输入一个整数n（其实输入不输入无所谓），然后立即输出结果，F（n）=1/2.

      也许有的人说这也算是程序吗？根本就没有计算啊。其实不要小看了这个程序，要知道，你能写出这个结果必然是经过了上述一系列复杂的运算的结果。就比如说有人让你计算1+2+。。。+100，你肯定不会傻乎乎的一个一个去加，而会选择公式（1+100）*100/2，这就是因为你已经知道他们是等价的了，所以不需要傻乎乎的加100次。这些是前人劳动的成果，而我们的劳动成果也就体现在了最简单的输出上。

 

      所以，好多很复杂的问题都有非常简单美观的输出，这正是算法的魅力！

评论

2 楼 celebration 2008-07-08  

谢谢rmn190的评论，我对于你说的两个问题也有些自己的感受
1.其实我也一直都非常的喜欢算法，我最喜欢的职业其实是算法工程师。虽然现在计算机硬件发展的速度越来越快，可是算法还是非常重要的。比如搜索引擎，要在茫茫的网络中搜索到需要的信息，对于算法的要求不言而喻。还有比如天气预报的计算等其他非常有价值的计算，现在的计算机的速度还是很慢。嵌入式编程，网络游戏和手机软件的开发等，由于硬件的限制，对于速度的要求也很高。总之算法是很重要的，即使在硬件发展速度飞快的今天。

2.对于你外甥所说的累，我觉得可能他还是对于这个东西不太感兴趣。一旦感兴趣，即使再累也会很高兴的，“累并快乐着”，呵呵。现在想想自己从小学开始就整天抱着数学奥赛的书啃，周六日也不休息，去参加市里的奥赛培训班，真的是累并快乐着。后来学习物理的时候也非常感兴趣，也没事就拿着物理竞赛的书啃。

1 楼 rmn190 2008-07-08  

看了博主的文章,我明白了两个问题:
    1, 更深层次在体会到算法所涉及的方面与一般的编程工作所涉及的有很大同.日常的编程工作更多地是要去熟悉业务流程,要去熟悉怎么用现用的框架来实现(如有兴趣的话还可以看看这些框架在背后是怎么实现的).而算法问题所涉及到的更像是把人类所有难题都一鼓脑地交给算法工程师,他们思考怎么能找出解决方案并用编程语言来告诉笨的只会干活的计算机去执行,当然在设计解决方案时也要考虑到其可行性(内存优化,时间优化),不然那个笨笨的计算机是不会自己"能动"地自行解决,只会很不友好地"暴"出:内存已耗尽!

    2, 为什么今年一个外甥高考完报志愿时不想学计算机.他的理由是很累太累,我当时也没能很好地说服他.现在明白了,搞计算机很累有两个方面:第一个也就是上面提到的"人类所有的难题",同时又是让那个很笨很笨的计算机来执行,这就要求工程师(主要是算法工程师)把事想的很周到,这个很周到就与人的本性有些想违背了,这样一有违背自然也就感觉累了;第二个原因也是基于人要与计算机合作,若不涉及到计算机时的人与人合作时,人是可以"心有灵犀"地去猜的,而计算机就不行了,这就要求所有与计算机打交道的人都得很规范,而这个规范又违背了人的本性,这样又累了.