主題
題目連結：
題目大意：
輸入有多列，每列給定一正整數 n （2 ≦ n ≦ 1000，當 n ＝ 0 時代表輸入結束），代表有 n 個人（編號為 1 ～ n）。現在有 n 個座位，而這 n 個人從編號 1 開始要依序入座。
編號 2 ～ 編號 n 的人都知道自己的位置在哪，唯獨編號 1 那個人不知道。所以編號 1 的會隨機選一個位置坐。接著換編號 2 ，如果他的位置沒有人坐，則就會坐在該位置；如果屬於他的位置被其他人坐了則他也隨機挑別的座位坐。以此類推。
試問，第 n 個人準備入座時，發現自己的位置已經有人坐的機率為何？機率之輸出格式為 a/b ，且 a/b 為最簡分數。
範例輸入：
2
0
範例輸出：
1/2
解題思維：
假設座位的編號也是 1 ～ n ，且對應到人的編號 1 ～ n ，並假設我們已經知道當只有 2 、 3 、 …… 、 n - 1 人時，第 2 、 3 、 …… 、 n - 1 個人入座時發現自己位置被占的機率。
因為編號 1 的人不知道自己的位置，所以會從座位編號 1 ～ n 隨便挑一個坐。以下探討編號 1 的入座情形：
當坐到編號 1 的位置時，該位置正好是編號 1 的人之座位。因此其後的人，編號 2 、 3 、 …… 、 n 都一定會坐在自己的位置上（因為他們知道自己的位置）。所以這個情況下，編號 n 的人不可能坐不到自己的位置。
當坐到編號 2 的位置時，編號 2 要入座時也會隨機挑位置坐（因為自己的被坐走了）。此時倘若我們將編號 1 的人以及編號 2 的位置移除掉，剩下的等價於本來就只有 n - 1 人（將剩下的人以及位置重新編號為 1 ～ n - 1 即可）的情況。所以這個情況的機率為 (1 ÷ n) × (人數為 n - 1 人時的機率)。
當坐到編號 3 的位置時，編號 2 會坐在自己的位置上，但編號 3 的就會隨機挑。此時等價於只有 n - 2 人的情況，此條路線的機率 (1 ÷ n) × (人數為 n - 2 人時的機率)。
……
當坐到編號 n - 1 的位置時，編號 2 ～ n - 2 都會坐在自己的位置上，但編號 n - 1 的就會隨機挑。此時等價於只有 2 人的情況，此條路線的機率 (1 ÷ n) × (人數為 2 人時的機率)。
當坐到編號 n 的位置時，編號 2 ～ n - 1 都在自己的位置上，唯獨編號 n 的人沒有。機率為 (1 ÷ n) 。
因此，所求機率為 0 + (1 ÷ n) × (人數為 n - 1 人時的機率) + (1 ÷ n) × (人數為 n - 2 人時的機率) + …… + (1 ÷ n) × (人數為 n - 2 人時的機率) + (1 ÷ n)。
所以已知人數為 2 人時，所求機率是 (1 ÷ 2) 。因此，推得人數 3 人時機率為 (1 ÷ 2) 、進而推得人數 4 人時機率為 (1 ÷ 2) 、 5 人機率為 (1 ÷ 2) 、 ……，可以看到不管人數為多少，機率都維持在二分之一。因此，每輸入一個 n （除非 n ＝ 0），輸出「1/2」即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
