Josephus Problem

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

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

Josephus Problem: Simulation

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

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

bool live[100]; // 紀錄哪些人是活人 // 找出下一個活人 int next(int& p) { while (!live[p]) p++, p%=n; p++, p%=n; } void josephus(int n, int m) { // 一開始所有人都活著 for (int i=0; i<n; ++i) live[i] = true; int p = 0; // 開始數的地方 for (int man = n; man > 1; --man) { // 再數 m-1 個人（第一個人剛剛已經數了） for (int i=0; i<m-1; ++i) next(p); // for (int i=0; i<(m-1)%man; ++i) next(p); live[p] = false; // 第 m 個人害羞的跑開了 next(p); // 從下一個開始數 } // 找出那個還活著的人 int answer = 0; next(answer); cout << "存活的人是" << answer << "號" << endl; }

UVa 133 305 402 10015

Josephus Problem: Modeling

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

void josephus(int n, int m) { // 將 n 個人放進 queue Queue queue; for (int i=0; i<n; ++i) queue.push(i); int answer; while (!queue.empty()) { // pop 和 push m-1 人 for (int i=0; i<m-1; ++i) queue.push(queue.pop()); // 第 m 個人 pop 出來後就不放回去 answer = queue.pop(); } cout << "存活的人是" << answer << "號" << endl; }

Josephus Problem: Dynamic Programming

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

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

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

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

// bottom-up DP void josephus(int n, int m) { int answer = 0; for (int i=1; i<=n; ++i) answer = (answer + m) % i; cout << "存活的人是" << answer << "號" << endl; }

UVa 151 440 10940 11351

Josephus Problem: Dynamic Programming

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

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