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次。这些是前人劳动的成果,而我们的劳动成果也就体现在了最简单的输出上。
所以,好多很复杂的问题都有非常简单美观的输出,这正是算法的魅力!
分享到:
相关推荐
"Oracle常用傻瓜问题1000问"显然是一部针对初学者和中级用户设计的指南,涵盖了日常工作中可能遇到的各种常见问题。在这个文档中,我们可以预见到一系列关于安装、配置、管理、查询优化以及故障排查的问答。 1. **...
ORACLE常用傻瓜问题1000问: 1. Oracle安裝完成后的初始口令? internal/oracle sys/change_on_install system/manager scott/tiger sysman/oem_temp 2. ORACLE9IAS WEB CACHE的初始默认用户和密码...
"Oracle常用傻瓜问题1000问"很显然是一份针对初学者或有一定基础但需要解决常见问题的用户编写的参考资料。这份文档可能涵盖了从安装配置到日常运维,再到SQL查询和性能优化等多方面的内容。 1. **安装与配置**: ...
484341266059730山海傻瓜助手3.17版(修复微信拼图不识别问题).apk
局域网共享问题解决 傻瓜解决方案 只须下载然后运行,所有问题点确定即可 安装完成以后只需连接居域网即可
Oracle常用傻瓜问题1000问 《Oracle常用傻瓜问题1000问》内容提要: 大家在应用ORACLE的时候可能会遇到很多看起来不难的问题, 特别对新手来说, 今天我简单把它总结一下, 发布给大家, 希望对大家有帮助! 和大家一起...
该书为“傻瓜系列”丛书之一,旨在帮助读者轻松应对各种面试问题。书籍详细地讲解了如何在面试中表现出色,针对不同类型的面试问题给出了实用的回答策略。 ### 二、版权信息 - **版权所有**:该书的版权由John ...
【傻瓜签名设计软件】是一款用户友好的个人签名设计工具,专为那些不具备专业设计技能但希望通过简单方式创建个性化签名的用户设计。该软件的独特之处在于它的易用性,正如其名“傻瓜”所暗示的,使得任何人都能轻松...
本文主要介绍了Zabbix在CentOS 7环境下的半傻瓜式安装方法,包括如何配置离线源进行安装、如何验证和安装Zabbix所需的各种依赖,以及如何理解Zabbix的主动和被动模式。 ### Zabbix版本兼容性 Zabbix的不同版本间...
傻瓜进销存 1.89破解\傻瓜进销存 1.89 注册机.rar ) 经测试可以注册成功
在"ORACLE傻瓜问题1000问"中,包含了多个关于Oracle安装、配置、管理和使用的常见问题。以下是一些关键知识点的详细解释: 1. **Oracle初始口令**:Oracle数据库在安装后,会设置几个默认的系统用户,如`internal/...
ORACLE 应用常见傻瓜问题 1000 问
"ORACLE应用常见傻瓜问题1000问"很可能是一本汇集了Oracle使用过程中遇到的各种常见问题及其解答的资源,旨在帮助用户解决日常操作中的困扰。下面,我们将深入探讨一些Oracle应用中可能遇到的关键问题和知识点。 1....
"说明_Readme.html"是安装程序的说明文档,用户在安装过程中可能会遇到的问题、步骤说明、注意事项和常见问题解答通常都会包含在这个文件中。阅读此文件可以帮助用户了解如何正确安装和使用该程序,解决可能出现的...
"ORACLE常用傻瓜问题1000问全集"显然是一部针对Oracle初学者和中级用户的问题集,旨在帮助他们解决日常遇到的各种疑惑。下面我们将深入探讨其中可能涉及的一些关键知识点。 1. **Oracle基础知识**: - 数据库概念...
3. **调试功能**:可能包含查看和记录HTTP请求和响应的能力,便于分析通信过程中的问题。 4. **模拟响应**:允许设置预定义的HTTP响应,方便测试不同状态码和响应头的情况。 5. **跨平台**:尽管这里提到的是Windows...