題目連結:
給定兩正整數 n 、 k (1 ≦ k ≦ n ≦ 100, 000),代表現在有 n 個人在玩「約瑟夫問題」(Josephus's Problem)的遊戲——也就是從編號一的人開始數 k 位,第 k 位的人淘汰出局。重複此步驟(跳過已淘汰的人)直到剩下一人。
求最後剩下的人之編號為何?
約瑟夫(或稱約瑟夫斯)問題之解法是很經典的遞迴解法(對於 k = 2 之歸納法,可見
維基頁面,可以試著從中推廣到任意 k 值),即:
Jn, k = (Jn-1, k + k) mod n
其中 Jn, k 代表有 n 個人數 k 位的約瑟夫問題下,最後剩下的人之號碼(從 0 開始)。而邊界條件為 J1, k = 0。因為本來就只有一個人,理所當然的就會活著。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。