主題
題目連結(jié)：
題目意譯：
n 位乘客上了一架有恰好 n 個(gè)座位的飛機(jī)。第一位乘客的票遺失了，所以他隨便挑了一個(gè)座位。而這之後，其餘乘客將會：
如果他們自己的座位還沒有被佔(zhàn)據(jù)，則他們會挑該座位坐；
反之，則他們會隨機(jī)挑座位坐。
回傳第 n 位乘客恰好坐在他自己座位上的機(jī)率。
限制：
1 ≦ n ≦ 10 ^ 5
範(fàn)例測資：
範(fàn)例 1：
輸入： n = 1
輸出： 1.00000
解釋： 第一位乘客只能挑第一個(gè)座位。
範(fàn)例 2：
輸入： n = 2
輸出： 0.50000
解釋： 第二個(gè)人有 0.5 的機(jī)率坐到第二個(gè)座位（即當(dāng)?shù)谝粋€(gè)人坐到第一個(gè)座位時(shí)）。
解題思維：
可以看到 n = 1 時(shí)，機(jī)率為 1；而 n ≧ 2 時(shí)，機(jī)率固定為 0.5。
因?yàn)閷兑话愕?n 值（令其機(jī)率值為 P(n)），我們可以看到對於第一位乘客來說會有以下情況：
挑到 1 號位；則剩下的人都會坐自己的座位。機(jī)率是 (1 / n)。
挑到 2 號位；則可以將剩下的人重新編號為 1 ~ n - 1（因此原本的第二位乘客取代了第一位乘客的角色）。因此機(jī)率為 (1 / n) × P(n - 1)。
挑到 3 號位；第二位乘客會坐在自己的座位上。而剩下的人跟上面同理可以重新編號成 1 ~ n - 2。因此機(jī)率為 (1 / n) × P(n - 2)。
挑到 4 號位；第二位和第三位乘客會坐在自己的座位上。而剩下的人重新編號成 1 ~ n - 3。因此機(jī)率為 (1 / n) × P(n - 3)。
……以此類推。
因此機(jī)率為 (1 / n) × (1 + P(n - 1) + P(n - 2) + …… + P(2))。
而我們可以用數(shù)學(xué)歸納法證明 P(n) = 0.5。
因?yàn)?P(2) = 0.5（基礎(chǔ)條件）；
而 n > 2 時(shí)有 (1 + 0.5 + 0.5 + …… + 0.5) / n = (1 + 0.5 × (n - 2)) / n = n / (2n) = 0.5。
故命題成立。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達(dá)人
