切換
舊版
前往
大廳
主題

ZeroJudge - c312: PD:死亡之塔 解題心得

Not In My Back Yard | 2019-06-23 23:25:50 | 巴幣 0 | 人氣 321

題目連結:


題目大意:
給定兩正整數 n 、 k (1 ≦ k ≦ n ≦ 100, 000),代表現在有 n 個人在玩「約瑟夫問題」(Josephus's Problem)的遊戲——也就是從編號一的人開始數 k 位,第 k 位的人淘汰出局。重複此步驟(跳過已淘汰的人)直到剩下一人。

求最後剩下的人之編號為何?



範例輸入:
5 1
7 2


範例輸出:
5
7


解題思維:
約瑟夫(或稱約瑟夫斯)問題之解法是很經典的遞迴解法(對於 k = 2 之歸納法,可見維基頁面,可以試著從中推廣到任意 k 值),即:
n, k = (Jn-1, k + k) mod n
其中 Jn, k 代表有 n 個人數 k 位的約瑟夫問題下,最後剩下的人之號碼(從 0 開始)。而邊界條件為 J1, k = 0。因為本來就只有一個人,理所當然的就會活著。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作