下午和朋友聊天的時(shí)候牺丙，有朋友提到了約瑟夫環(huán)問題则涯。你和另外 n-1 個(gè)人圍成一個(gè)圈，按 1，2粟判，...肖揣，n 依次編號(hào)。第一個(gè)人從 1 開始報(bào)數(shù)浮入，數(shù)到 k 的人會(huì)被殺掉龙优，然后下一個(gè)人重新從 1 開始報(bào)數(shù)。如此往復(fù)事秀，直到最后只剩下一個(gè)人彤断。問題是，你應(yīng)該如何選擇自己的初始位置易迹，才能保證最后不被殺掉呢宰衙？
速度越快的算法當(dāng)然越好，畢竟這是一個(gè)生死攸關(guān)的問題睹欲。下面你將會(huì)看到供炼，我們?nèi)绾瓮ㄟ^一些基本的數(shù)學(xué)推導(dǎo)最終得到這個(gè)問題的遞推解。
初步思考
考慮這樣一種相對(duì)簡(jiǎn)單的情況：總共有 5 個(gè)人窘疮，數(shù)到 3 的人被殺掉袋哼。那么，死亡過程如下圖所示：
經(jīng)過一番模擬之后涛贯，我們已經(jīng)對(duì)約瑟夫環(huán)問題有了一個(gè)大概的直觀理解。下面蔚出，嘗試使用數(shù)學(xué)語言來描述這個(gè)問題弟翘。
哦對(duì)了，假如圓圈里只有你自己骄酗，那么你肯定就是最后的幸存者稀余，這是一個(gè)極其有用的特殊情況。
建立模型
這些是我們的已知條件：
- 總共有 n 個(gè)人趋翻；
- 數(shù)到 k 的人將被殺死睛琳。
這個(gè)是我們的未知數(shù)：
- 位置 p，處在位置 p 上的人將會(huì)幸存下來嘿歌。
推導(dǎo)求解
現(xiàn)在考慮一種泛化情形：總共有 n 個(gè)人掸掏，數(shù)到 k 的人被殺掉茁影，其中 n >= k宙帝。幸存者的位置為 pn 。
顯而易見募闲，初始位置為 k 的人將會(huì)第一個(gè)被殺掉步脓。此時(shí)，經(jīng)過重新排序之后，問題變成了 n-1 個(gè)人的情形靴患。幸存者的位置為 pn-1 仍侥。如果能夠找到從 pn-1 到 pn 的遞推關(guān)系，那么問題就解決了鸳君。
重新排序之后，每個(gè)人的位置發(fā)生了下面這些變化：
- 1 -> n-k+1
- 2 -> n-k+2
- ...
- k-1 -> n-1
- k 被殺死
- k+1 -> 1
- ...
- pn -> pn-1
- ...
- n-1 -> n-k+1
- n -> n-k
很容易我們能得到這樣一個(gè)關(guān)系式：pn = (pn-1 + k) % n 或颊。再加上剛才討論的特例砸紊，只有一個(gè)人的情況時(shí)，p1 = 1 囱挑。遞推式就已經(jīng)很明顯了醉顽。
當(dāng)然上文只討論了 n>=k 的情形，實(shí)際上對(duì)于 n<k 的情形平挑，剛才所得到的遞推式依然適用游添，我們就不展開討論了。
編碼實(shí)現(xiàn)
既然遞推式這么簡(jiǎn)潔明確通熄，那么編碼實(shí)現(xiàn)就不用寫了吧唆涝？
