作者qmxlf (dfksk )
看板Inference
标题Re: [问题] 微软面试题
时间Mon Jul 18 19:09:31 2005
很经典的推理方法
※ 引述《libooo (libooo)》之铭言：
: ※ 引述《Nanan (安庆程二)》之铭言：
: : 不知道有没有人发过。
: : 题目如下：
: : 飞机上有100个座位，按顺序从1到100编号。有100个乘客，他们分别拿到了从1号到100
: : 号的座位，他们按号码顺序登机并应当对号入座，如果他们发现对应号座位被别人坐
: : 了，他会在剩下空的座位随便挑一个坐。现在假如1号乘客疯了 -_-! (其他人没疯)，他会
: : 在100个座位中随机座一个座位。那么第100人正确坐自己坐位的概率是多少？
: : 注意登机是从1到100按顺序的。
: 先从只有两人看起
: 很明显最後一人坐对的机率是2分之1
: 接着看三人的情况
: 1号可以有3种选择:
: a. 坐到1号位
: 则3号一定坐对 机率为 1/3*1
: b. 坐到2号位
: 那剩下的可能性就变成类似两人的情况
: 只是1号位可以视为2号的正确位置
: 得机率为 1/3*1/2
: c. 坐到三号位
: 机率为 0
: 把三种情况机率相加 1/3 + 1/3*1/2 = 1/2
: 接着就可以利用数学归纳法
: 设当 x<n , x 皆成立时
: 若1号坐到第x号
: 那剩下的可能性就变成类似只有x人的情况
: 而x<n的机率已经设为1/2
: 所以最後一人坐对的机率为
: ( 1 + 1/2*(n-2) ) / n = 1/2
: 得证
: 希望大家看的懂这个烂烂的解法orz....
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.243.43.30