Josephus Problem

Josephus Problem

有n個人圍成一圈,現在從第一個人開始報數,數到第m人時,就殺掉這第m人;然後從被殺的下一位繼續重新報數,數到第m人時,就殺掉這第m人。如此不斷數m人、殺此人,直到最後會剩下一個人,請問他是誰?

這個美式風格的問題似乎有點殘酷。如果改成「不斷數m個人,被點名的人就臉頰泛紅,害羞的跑開了」這樣應該會童真一點。

Josephus Problem: Simulation

直接模擬「不斷數m個人,被點名的人就臉頰泛紅,害羞的跑開了」這個行為。時間複雜度為 O(nm)。

有個加速的小手段是:當要數的人數超過實際人數時,可以取一下模數。

UVa 133 305 402 10015

Josephus Problem: Modeling

數人和殺人的動作可以整合成queue的操作。首先把每個人依序放進queue,然後只要連續的pop和push m-1人,於pop第m人時,不要將他放回queue裡面,這樣就成功的模擬了!時間複雜度為 O(nm)。實作時可以使用circular queue節省記憶體空間。

Josephus Problem: Dynamic Programming

除去一人之後,剩下來的人重新編號,就變成了子問題了。觀察原編號和新編號的關係,可得到一遞迴公式:

f(n, m) = (f(n-1, m) + m) % n
f(1, m) = 0;

f(n, m):最後活下來的人的編號。

用此遞迴公式進行計算,時間複雜度為O(n)。

UVa 151 440 10940 11351

Josephus Problem: Dynamic Programming

這裡提供一個狀似目前最快的方法,感謝網友提供:http://citeseer.ist.psu.edu/gelgi02time.html

另外各位也可以看看高德納先生的TAOCP,裡面對Josephus Problem也有諸多描述。