微軟面試題 - 推理遊戲

※ 引述《Nanan (安慶程二)》之銘言：
: 不知道有沒有人發過。
: 題目如下：
: 飛机上有100個座位，按順序從1到100編號。有100個乘客，他們分別拿到了從1號到100
: 號的座位，他們按號碼順序登机并應當對號入座，如果他們發現對應號座位被別人坐
: 了，他會在剩下空的座位隨便挑一個坐。現在假如1號乘客瘋了 -_-! (其他人沒瘋)，他會
: 在100個座位中隨机座一個座位。那么第100人正确坐自己坐位的概率是多少？
: 注意登机是從1到100按順序的。
第一次來這個板
po一下我的想法 如果有重複請跟我說我會自d

首先一個簡單概念:
不管是誰 要坐到1號位子或100號位子的機率是一樣的
而坐到1號位子就代表最後100號位會是正確的
坐到100號 錯誤

再來除了坐到1號或100號的情況
我們假設一開始的1號做到了X號的位子
所以2,3,4,...(X-1)號都會坐在正確的位子
而輪到X時 他就會變成所謂的 "新的瘋子"
一樣有同樣的機會坐在代表"正確"的1號
以及同樣的機會坐在代表"失敗"的100號

如果他坐在1或100號之外的位子
那麼就將他坐到的位子設為新的X 之後同理
由於X只會越來越大 所以最慢最慢也是逼到 X=99 就結束了 (剩1跟100空..1/2)

====
其實一開始提到的那個觀念是重點
剩下來的嚴格上來講都有點算贅言
((只要一句"其他情況這個問題就會繼續"就夠了))
不過怕我表達能力不好所以多寫一點
歡迎指正錯誤 <(_ _)>

--