疯狂的乘客

2009-11-02 14:52:14 来自: 睡神(是谁在风中飘)

飞机上的100个座位被分配给100个乘客，每个乘客拿到唯一的一个号码。乘客们按照如下方法找座位：第一个乘客随机选一个座位坐下，从第二个乘客起，如果该乘客的座位没人坐，则该乘客对号入座；否则，该乘客随机选一个座位坐。
问：第100个乘客有多大机会坐在自己的座位上？

2009-11-02 15:13:05 大饼博士 (我感谢你八辈祖宗)

占沙发等答案

> 删除
2009-11-02 15:55:27 Ring (第一轮结束，第二轮开始)

太经典的问题了，我看了几年这个问题了。说实话，现在还不是很清楚，每次都听到不同的答案。等概率大师出马吧。

> 删除
2009-11-06 18:01:10 特蘭斐的遺跡

可以用程序模拟吗？

> 删除
2009-11-08 18:46:08 睡神 (是谁在风中飘)

当然可以，不过要写出程序，难道不需要先对问题建立数学模型吗？

> 删除
2009-11-12 15:26:43 Shurrik

我当年应聘flashget，技术总监给我出的题

> 删除
2009-11-12 15:30:29 荒野 (对撞生新态)

前几天水木上还有人问过这个题，招聘的季节。。。

> 删除
2009-11-12 16:21:46 Shurrik

python代码：
from random import randint
n=100000
count=0
list=[]
for i in xrange(n):
list=range(0,100)
r=randint(0,99)
if r==0:
count+=1
elif r==99:
continue
else:
del list[r]
for j in xrange(len(list)-1):
m=randint(0,len(list)-1)
if m==len(list)-1:
break
del list[m]
if list[0]==99:
count+=1
print '%f%%' %((float(count)/n)*100)

一次执行结果：
>>>
2.001000%

> 删除
2009-11-12 16:25:34 Shurrik

豆瓣不支持缩进，贴我je上了
http://darklipeng.javaeye.com/admin/blogs/515440

> 删除
2009-11-12 22:43:45 荒野 (对撞生新态)

发信人: timepp ([m), 信区: IQDoor
标题: Re: 同学发过来的一道微软智力面试题
发信站: 水木社区 (Fri Jun 3 15:56:17 2005), 站内

首先，第100个人上飞机时，可能的空位只能是1号或100号。

1. 如果第一个人坐了1号，那么此时空的是100号。
2. 如果第一个人坐了100号，那么此时空的是1号。
3. 如果第一个人坐了2-99中的某一个：
2-99个人开始复杂的找坐位的过程，不管怎么复杂，最后都只会剩下1号或100号。而"1"和"100"对于整个过程是对称的。1和100这两个坐位对于2-99个人来说，都没过超过另一个的特殊性。从而，最后剩下1号和最后剩下100号的机率各占一半。

综上，第100个人上飞机是，1号空的概率=100号空的概率。都为50%

> 删除
2009-11-12 22:45:44 荒野 (对撞生新态)

http://www.newsmth.net/bbstcon.php?board=IQDoor&gid=61015

> 删除
2009-11-13 10:01:19 Shurrik

如果问题要变成这样，当初那个人也没考我的必要，数学方式都能解出

> 删除
2009-11-13 10:09:12 Shurrik

恩，我没仔细看，当初那个人给我讲的不是这样。是如果第一个人坐错位子，那么其他人就也随机从其余的找位子。

> 删除