微軟面試題 - 推理遊戲

※ 引述《Nanan (安慶程二)》之銘言：
: 不知道有沒有人發過。
: 題目如下：
: 飛机上有100個座位，按順序從1到100編號。有100個乘客，他們分別拿到了從1號到100
: 號的座位，他們按號碼順序登机并應當對號入座，如果他們發現對應號座位被別人坐
: 了，他會在剩下空的座位隨便挑一個坐。現在假如1號乘客瘋了 -_-! (其他人沒瘋)，他會
: 在100個座位中隨机座一個座位。那么第100人正确坐自己坐位的概率是多少？
: 注意登机是從1到100按順序的。
考慮下面規則
1→23→56→81→96→1
這表示1號人坐到23號位置(2號以後到22號都可坐自己的位置)
而23號人沒23號位置坐而坐到56號位置
依序56號人坐到81號位置
81號人坐到96號位置
96號人坐回1號位置
這個數字跟箭頭的搭配可構成一種坐法
再看一種坐法
1→3→59→83→90→100→1
這種坐法很明顯表示100號人只剩1號位置可坐而坐到1號位置
現在我們要求的是
在所有的坐法中100號人不會坐到1號位置(100號人除了1號跟100號不可能坐到其它位置
因為之前的位置除了1號位置不是被佔去就是被自己的相同的號碼數的人給坐了)
的機率為何
先求(100→1的機率)/(所有可能的箭頭跟數字的排法) 我簡單的寫大家看懂即可
注意數字要遞增理由跟上面綠色字差不多(類似)
然而在所有排法中可區分為最後是(除了100的數字→1)跟(100→1)
在每個(除了100的數字→1)的情況下在其中加個100不就是(100→1)的情況了
例如上方的1→23→56→81→96→1在96跟1之間加個100
變成1→23→56→81→96→100→1
也就是說上面兩種情況的個數相同
即100號人坐到1號位置的機率是1/2(找不到百分..的符號~~a)
那不坐到1號位置也就是坐到100號位置的機率也是1/2

--