真冷清，我来说个题目把

Taeheebin(Now or Never)

2011-03-13 23:43:47

大家先自己想想，别急着翻答案。。。 一架飞机外，有100名乘客准备登机。飞机有100个座位。其中第一位准备登机的乘客没有带登机牌，所以他不知道坐那儿，于是他随便坐了。 后面的乘客按照自己登机牌的号码入座，当后面的乘客发现自己的座位被占了的时候，他也会选择从剩下的座位里随便选择一个坐。 问题是：最后一位登机的乘客坐到原本属于自己的位子的概率是多少？ (飞机有100个座位 )

赞

• 

  rascal (我是沉默的兴奋剂) 2011-03-14 00:14:28

  0.5?

  删除 |

  赞 回复
• 

  安布罗特斯死后 (in a nuts hell) 2011-03-14 00:50:51

  貌似确实是1/2 每一个迷茫的人，去1号或去100号的概率是一样的，总之最后就都1/2了。

  删除 |

  赞 回复
• 

  姿势科学 (农夫三拳猪又睡觉) 2011-03-14 00:58:53

  Σ(1/A(100,k))，k取从1到99.

  删除 |

  赞 回复
• 

  姿势科学 (农夫三拳猪又睡觉) 2011-03-14 01:03:32

  或者写成 (99!+98!+…+1!)/100!

  删除 |

  赞 回复
• 

  姿势科学 (农夫三拳猪又睡觉) 2011-03-14 01:11:19

  问题换成n个座位n个旅客的话，要求的概率记为p(n),貌似 p(n)=1/n+1/n*p(n-1).(n≥3) p(2)=1/2. 原题要求的就是p(100).

  删除 |

  赞 回复
• 

  安布罗特斯死后 (in a nuts hell) 2011-03-14 01:19:32

  经验算n=3得1/2，你的结果也一样。继续验算n=4情况，仍是1/4+1/41/3+1/41/31/2+1/41/2 = 1/2。你的是3/8。所以你的算错了~~

  删除 |

  赞 回复
• 

  姿势科学 (农夫三拳猪又睡觉) 2011-03-14 01:23:41

  你算式里面的“1/4*1/2”代表什么？

  删除 |

  赞 回复
• 

  我思故我在 (12+34*56+7+89) 2011-03-14 01:27:01

  [内容不可见]

  删除 |

  赞 回复
• 

  安布罗特斯死后 (in a nuts hell) 2011-03-14 01:28:04

  公布思路吧，方便起见给乘客编号，按登记顺序记为1,2……n号。相应飞机上相应有乘客各自的1,2……n号座位。1号乘客的选择有1、n、其他号座位，1、n的概率是一样的。如果选了其他，那么那个人被占了，只能选择1、n、剩下的其他座。然后1、n的概率还是一样的。这个过程里只要有人占了1座，那么n客就赢了，否则n客就输了，两者概率始终一样。如果过程一直下去到了最后一个人，剩下的就只剩1座和n座了，那还是各自1/2。总之就是1/2。

  删除 |

  赞 回复
• 

  我思故我在 (12+34*56+7+89) 2011-03-14 01:32:38

  [内容不可见]

  删除 |

  赞 回复
• 

  姿势科学 (农夫三拳猪又睡觉) 2011-03-14 01:33:03

  有人占了1，n客也未必赢吧？

  删除 |

  赞 回复
• 

  安布罗特斯死后 (in a nuts hell) 2011-03-14 01:37:44

  当然赢了。那个循环已经终止了。其他人各自就位了。

  删除 |

  赞 回复
• 

  希望豆瓣早倒闭 (求豆瓣把我封了吧 求你们了) 2011-03-14 01:38:03

  占1 错误就终止了

  删除 |

  赞 回复
• 

  [已注销] 2011-03-14 01:46:17

  [内容不可见]

  删除 |

  赞 回复
• 

  [已注销] 2011-03-14 01:49:47

  [内容不可见]

  删除 |

  赞 回复
• 

  我思故我在 (12+34*56+7+89) 2011-03-14 01:50:23

  [内容不可见]

  删除 |

  赞 回复
• 

  Mrlazy (Hello,Jarry.) 2011-03-14 01:51:47

  这个题目 的困惑 在哪里呢？ 就是形容 那个 位置可能被占的那个客人的时候少了 少了 个 最 字。

  当最后面的乘客发现自己的座位被占了的时候，他也会选择从剩下的座位里随便选择一个坐。

  如果是这样，估计大家都能马上的回答出是1/2

  删除 |

  赞 回复
• 

  我思故我在 (12+34*56+7+89) 2011-03-14 01:54:56

  [内容不可见]

  删除 |

  赞 回复
• 

  姿势科学 (农夫三拳猪又睡觉) 2011-03-14 01:55:04

  我是算错了

  删除 |

  赞 回复
• 

  [已注销] 2011-03-14 01:59:39

  [内容不可见]

  删除 |

  赞 回复
• 

  Taeheebin (Now or Never) 楼主 2011-03-14 02:14:03

  @neophyte 俺真羡慕用e文作答的童鞋 ^^ 当然，你说的完全正确，就你说的方法导出一个递推式，初值p(2)=1/2.结论当然是不管多少乘客都是1/2. 这是一般思维很自然想出的一种方法。 还有一种方法，比较巧。 假设所求概率为P,假设事件A是第一个乘客坐到自己位置上，事件B是第一个乘客坐到最后一个乘客的位置上，事件C是第一个乘客坐到第2个至99个乘客的位置上，事件D是第2个至第99个乘客都没有坐到最后一个乘客的位置上，事件E是第2个至第99个乘客都没有坐到第一个乘客的位置上。 那么可以得到 P =P(A) + P(CD)假如事件C发生了，而最后一个乘客的座位被第2个至第99个乘客其中一个占了的话，那么他只能去坐第一个乘客的位置。所以 1-P=P(B) + P(CE). 而P(A)=P(B)，P(CD)=P(CE)，所以可以得到 P=1-P，也就是P=1/2。

  删除 |

  赞 回复
• 

  Taeheebin (Now or Never) 楼主 2011-03-14 02:17:17

  @ 淫是YD的淫 那你程序设置的肯定有问题，很容易举出反例。

  删除 |

  赞 回复
• 

  我思故我在 (12+34*56+7+89) 2011-03-14 02:30:13

  [内容不可见]

  删除 |

  赞 回复
• 

  姿势科学 (农夫三拳猪又睡觉) 2011-03-14 02:30:41

  MooN提出的巧方法，只是省略了一些分析过程，“P(A)=P(B)，P(CD)=P(CE)”的具体来源，就是陈默的分析思路。 要省略的话，甚至可以直接说第一个座位和最后一个座位的地位是对等的。

  删除 |

  赞 回复
• 

  [已注销] 2011-03-14 02:34:12

  [内容不可见]

  删除 |

  赞 回复
• 

  [已注销] 2011-03-14 02:37:51

  [内容不可见]

  删除 |

  赞 回复
• 

  Taeheebin (Now or Never) 楼主 2011-03-14 03:06:46

  @ 淫是YD的淫 有点迷糊，没看懂，我再看看。 都是夜猫子啊，我今天熬夜时为了看巴萨的比赛，你们熬夜做神马？

  删除 |

  赞 回复
• 

  Taeheebin (Now or Never) 楼主 2011-03-14 03:18:21

  @ 淫是YD的淫

  你这个式子 p(n)(n) = 1 - Sum{p(i)(n),1≤i＜n} 是想表达n个人乘客的情形第n个乘客作对的概率。 但是你给出的初始条件是：p(1)(j) = 1/100 , j = 1,2,...,100 而事实上在n=2时，p(1)(2)≠1/100，而是1/2.

  删除 |

  赞 回复
• 

  Taeheebin (Now or Never) 楼主 2011-03-14 03:24:49

  @ 陈默 你公布的思路没有说服我。

  删除 |

  赞 回复
• 

  我思故我在 (12+34*56+7+89) 2011-03-14 03:38:57

  [内容不可见]

  删除 |

  赞 回复
• 

  Taeheebin (Now or Never) 楼主 2011-03-14 03:41:48

  @陈默 重新看了看，这样表达稍有模糊，但思路没错，所以 p=1-p,从而 p=1/2.

  删除 |

  赞 回复
• 

  我思故我在 (12+34*56+7+89) 2011-03-14 03:46:43

  [内容不可见]

  删除 |

  赞 回复
• 

  Mrlazy (Hello,Jarry.) 2011-03-14 03:49:28

  2011-03-14 01:59:39 neophyte (有些事不用一個晚上做完) @Mrlazy, 按你說的，請問第99位登机的乘客坐到原本属于自己的位子的概率是多少？ > 删除 .. 问题不完整，更改之后，题目的意思是，第一个人随便坐下去，剩下的2-98都能够坐到自己的位置，99和100不确定？还是 2-98加上100坐在自己相应号码的位置，1 和 99 不确定（这种情况，答案还是1/2) 至于如果是99和100都不确定， 那答案 是 1/3

  删除 |

  赞 回复
• 

  Taeheebin (Now or Never) 楼主 2011-03-14 03:52:02

  @ 淫是YD的淫

  p(n)(n) = 1 - Sum{p(i)(n),1≤i＜n} 你这个式子是不是改成 p(n)(n) = 1 - Sum{p(i)(n),i ≠n}

  总之，这道题用计算机按你这种思路来解有些麻烦。

  删除 |

  赞 回复
• 

  Taeheebin (Now or Never) 楼主 2011-03-14 03:56:05

  @Mrlazy 这有什么不好理解的，第一个随便做，其他人有登机牌肯定是先找自己的那个位置，如果是空的，就坐下来；如果被占了，就随机的坐在其它空位置上。

  删除 |

  赞 回复
• 

  Taeheebin (Now or Never) 楼主 2011-03-14 03:57:04

  看球赛了，没人是巴萨迷吗？ 马上要开始了，看球赛去了 ^^

  删除 |

  赞 回复
• 

  我思故我在 (12+34*56+7+89) 2011-03-14 04:00:12

  [内容不可见]

  删除 |

  赞 回复
• 

  我思故我在 (12+34*56+7+89) 2011-03-14 04:07:17

  [内容不可见]

  删除 |

  赞 回复
• 

  安布罗特斯死后 (in a nuts hell) 2011-03-14 05:08:42

  是啊，我说的并没有很细致，因为剩下的细节想想就很清楚了……本来就是几个“错位 ”节点: 1客、a1客、a2客、……，最后终止于1座就形成了环，终止于n座就是另一个环，两边始终是等概率的……画图会更清晰点不过没什么必要……

  删除 |

  赞 回复
• 

  豆友1158543 2011-03-14 13:05:08

  [内容不可见]

  删除 |

  赞 回复
• 

  豆友1158543 2011-03-14 13:13:22

  [内容不可见]

  删除 |

  赞 回复
• 

  豆友1158543 2011-03-14 19:32:23

  [内容不可见]

  删除 |

  赞 回复
• 

  壶碟会上探花郎 (……) 2011-03-15 09:54:17

  微软出的编程之美里的例题，好像是叫金刚坐飞机

  删除 |

  赞 回复
• 

  包爽屌哥 2011-05-23 14:28:41

  设f（n）为n个乘客按照上述规则产生的座位方法的种数

  则 f（1） = 1 f（2） = 2

  然后对n 来说，对1号乘客的选择枚举可得 若选1号位， 则产生方法数为1 1 1 2 f(n-1) 3 f(n-2) .... n f(1)

  则 f（n） = 1 + f(1) + ... + f(n-1) 推出 f(n) = 2^(N-1)

  于是 f（99）/ f（100) = 1/2

  f（99）的情况下，前99个人刚好坐了99个座位，f（100）则是100人选座位的全部可能情况

  删除 |

  赞 回复
• 

  明生 (签什么名) 2011-05-23 14:48:13

  mark

  删除 |

  赞 回复
• 

  焓熵 (蛋似铁打 股如金刚) 2011-08-14 03:48:00

  第一个人占最后一个人座位的概率是1% 第二个人占最后一个人座位的概率是 第一个人占第二个人座位的概率* 1/99也就是 1/100 * 1/99 类推 所以我认为结果应该是

  1- 1% - 1%* 1/99 - 1% * 1/99 * 1/98 ......

  用计算机算出来的结果是0.989898

  删除 |

  赞 回复
• 

  TY (你的因果就是你的世界) 2011-08-14 12:41:37

  各种直觉…… 1/2 不像正确的答案。

  后续者的选择都应该在缩小随后出现占位情况的可能性，并有可能到某一人那里刚好清除。

  首先，从逻辑上，要排除并发（争位）的情形，这是不可计算的情形。于是问题就变成100次顺序选择的故事。

  第一个人：随机选位，坐对的机会只有1/100，占第二个人位置的机会也是1/100。 第二个人：有99/100的机会坐自己的位；有1/100的机会被占位， 其中又有1/99的机会刚好占了第三（或第n）人的位（1/100 * 1/99） 第三个人：面临三种情况 A 被第一个人占位：1/100 B 被第二个人占位：1/100 * 1/99 （第一人占第二人位，第二人又刚好占第三人位）， 其中，第三人刚好占下一个人位置的机会: (1/100 * 1/99) * 1/98 C 没被占位，几率是 1 - 1/100 - 1/100 * 1/99

  第四个人： 会被前面占位的情形包括： A 被第一个人占：1/100 B 被第二个人占：1/100 * 1/99 C 被第三个人占：1/100 * 1/99 * 1/98

  第N个人：各种貌似 1/100
  1/100 * 1/99
  1/100 * 1/99 * 1/98 ... 1/100 * 1/99 * ... 1/(100-N+2))

  ---

  (+) = ?

  在草稿里码了半天，来贴时发现与前面 @ 焓熵 的答案是一样的， 各种惭愧:-p

  删除 |

  赞 回复
• 

  姿势科学 (农夫三拳猪又睡觉) 2011-08-14 13:21:00

  楼上两位，你们从第3个人开始算错了。

  删除 |

  赞 回复
• 

  TY (你的因果就是你的世界) 2011-08-15 17:22:17

  好奇查了一下，如楼上一童鞋提示，原来是一本书《编程之美》中的题，叫做“金刚坐飞机”。

  仔细看了一下，帖主所述题目与书中所解（题2）不同。不知楼上各位童鞋是在解楼主出的题，还是早就知道“金刚坐飞机”这道题，在复述已知答案？

  删除 |

  赞 回复
• 

  姿势科学 (农夫三拳猪又睡觉) 2011-08-15 18:43:59

  没见过那题。

  删除 |

  赞 回复
• 

  [已注销] 2011-08-17 14:47:31

  [内容不可见]

  删除 |

  赞 回复
• 

  不离 (茕茕白兔、东走西顾) 2011-08-20 23:10:51

  当年我最烦做这种题了......... 一只没有攻克之

  删除 |

  赞 回复
• 

  [已注销] 2011-08-21 00:10:55

  [内容不可见]

  删除 |

  赞 回复
• 

  狂者 (理想。真实) 2011-08-21 00:59:43

  答案是：1-【1/100+1/(10099)+...+1/(10099...2)】 解析：中括号第一项代表第一个人是乱坐的，坐到最后一个人位子的概率自然是1/100；第二项表示第二个人坐在了最后一个人的位子上，首先既然是第二个人坐的，那么第一个人肯定坐在了别的位子上，由此有99/100，而第一个人肯定坐在了第二个人的位子上，所以第二个人才不得不离开自己的位子找别人的位子于是有(99/100)(1/99)，除了自己的被霸占了的位子，其余的位子自然还剩99个，那么坐到最后一个人的位子的概率则是（99/100）（1/99）（1/99）=1/(100*99)依次类推，就会有以上公式。

  删除 |

  赞 回复
• 

  狂者 (理想。真实) 2011-08-21 01:11:05

  而如果把题目的条件改为：第一个照样乱坐，从第二个起都去直接去找自己的座位，这时霸着自己座位的那个人就可以滚蛋了，那人便只好找其它座位去坐了。 如果是这样，可以看出全过程便只有第一个进飞机的人动来动去，于此最后的概率便是1/2。。。应该能说明此问题不能和LZ的问题等价吧~

  删除 |

  赞 回复

你的回复