微軟面試題 - 推理遊戲

Xanthe avatar
By Xanthe
at 2005-07-18T19:09

Table of Contents

很經典的推理方法

※ 引述《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....

--

All Comments

囚犯和燈

Hamiltion avatar
By Hamiltion
at 2005-07-18T18:46
※ 引述《Nanan (安慶程二)》之銘言： : 100個囚犯，101間牢房，每人一間， : 剩下的那間牢房里面有一盞燈 : 每天隨机叫一個囚犯去空房間一次，可以開燈，關燈，或者什么都不作 : 如果有一天，有一個囚犯說，我确定100個囚犯全都來過了 : 對了，就放了所有囚犯； : 錯了，就全殺。 : 所有囚犯 ...

囚犯和燈

Skylar Davis avatar
By Skylar Davis
at 2005-07-18T18:28
※ 引述《Nanan (安慶程二)》之銘言： : 100個囚犯，101間牢房，每人一間， : 剩下的那間牢房里面有一盞燈 : 每天隨机叫一個囚犯去空房間一次，可以開燈，關燈，或者什么都不作 : 如果有一天，有一個囚犯說，我确定100個囚犯全都來過了 : 對了，就放了所有囚犯； : 錯了，就全殺。 : 所有 ...

囚犯和燈

Todd Johnson avatar
By Todd Johnson
at 2005-07-18T16:51
100個囚犯，101間牢房，每人一間， 剩下的那間牢房里面有一盞燈 每天隨机叫一個囚犯去空房間一次，可以開燈，關燈，或者什么都不作 如果有一天，有一個囚犯說，我确定100個囚犯全都來過了 對了，就放了所有囚犯； 錯了，就全殺。 所有囚犯都看不見燈，除非走進空房間 囚犯之間不能互通消息，除非用燈 游戲開始之前 ...

微軟面試題

Anthony avatar
By Anthony
at 2005-07-18T06:05
※ 引述《talent (Iand#39;m back)》之銘言： : ※ 引述《greenmiracle (看著吧..)》之銘言： : 真的是個漂亮的解法!!!!! : 高手高手... ^_^ : : 例如上方的1→23→56→81→96→1在96跟1之間加個100 : : 變成1→23→5 ...

微軟面試題

Jacky avatar
By Jacky
at 2005-07-17T19:10
※ 引述《greenmiracle (看著吧..)》之銘言： 真的是個漂亮的解法!!!!! 高手高手... ^_^ : 例如上方的1→23→56→81→96→1在96跟1之間加個100 : 變成1→23→56→81→96→100→1 : 也就是說上面兩種情況的個數相同 我想要補充 ...