幾年前我在 C_andCPP 版發表了一篇 Josephus problem 的整理 #1AMqP2Cr 。
最近我又重新的研究了一下這問題，在這邊跟大家分享一下心得。
問題如下：
有 n 個人圍成一圈，並且依序編號為1 ~ n，從 1 開始數，每數 m 個
人就把此人由圈圈中刪除，一直持續此動作直到只剩下一個人為止。
問最後被剩下來的那個人是編號幾號。
簡單的使用 queue 或是 recursion 的解法就不介紹了，一般常見的解
法有四種：
1. Recursion 改成迴圈版 [1]
int ans = 0;
for (int = 2; i <= n; ++i)
ans = (ans + m) % i;
return ans + 1;
複雜度是 O(n)，而這方法也可以找出第 k 個被刪除的人的編號。
缺點是不管 m 是大還是小，這方法所需要的時間是一樣的。
2. 另一種 recursion 改成的迴圈版
版本 1 [3]
int answer = n * m;
while (answer > n)
answer += (answer - n - 1) / (m - 1) - n;
return answer;
版本 2 [4]
差別只是在計算方向不同，但是這版本比較慢，因為需要稍多運算。
int d = 1;
while (d <= (m - 1) * n)
d = 1 + (d * m - 1) / (m - 1);
return m * n + 1 - d;
這類方法因為需要計算 n * m 或是 n * (m - 1) ，所以當 n 和 m 都比較大時
會 integer overflow。
複雜度是 O(log_{m/(m-1)} (nm))
所以當 m 小的時候這方法會快很多，但是當 m 大時就很慢了。
3. 另一種 recursion [2]。
if (n < m) 用方法 2
jn = recursion 算出 (n - floor(n/m), m) 的答案
if (jn <= n % m) return jn + m * (n - floor(n/m))
else
jn -= n % m
return m * floor(jn / (m - 1)) + (jn % (m-1) == 0 ? -1 : jn % (m - 1))
複雜度 O(m + lg_{m/(m-1)} (n/m))，但是跟前面的方法不同，這方法
需要額外的空間來作 recursion 。
而且當 m 很大的時候，這方法很容易會 stackoverflow 因為 recursion 太深。
所以需要手動用 stack 模擬 recursion。
4. 方法 3 的迴圈版
我發現到 3 的方法其實有兩個階段，
一開始會一直 recusion ，而且過程中 m 是一直不變的，只有 n 值減小。
當 n 比 m 小時，直接使用方法 2 計算出答案，然後一層一層回推出原本 n 的答案。
所以我就嘗試著能不能用兩個迴圈來代替 recursion ，而不使用 stack 。
不過困難點是在於怎樣從下層的 n 回推出上層的 n 。
也就是考慮 recursion: (n, m) -> (n' = n - floor(n/m), m)
如何在只知道 n' 和 m 的情況下推出 n 。
不過很可惜的是光靠 n' 和 m 是沒辦法明確的決定 n 的。
因為 n 可能是 n' + n'/(m - 1) 也可能是 n' + n'/(m - 1) + 1
但是只有這兩種可能而已，而且後者發生的機率不高。
所以只要花一些空間紀錄 n = n' + n'/(m - 1) + 1 的資訊，在回推的時候就
可以順利的從 n' 和 m 推出 n 了。
不過我找不到 n = n' + n'/(m - 1) + 1 出現次數的上限，
不然就可以得到空間複雜度的上限了。
實驗
我測試了 n = 2^21 的情況。
當 m < 2^10 時，方法 2 最快。
當 2^10 < m < 2^15 方法 4 最快。
當 m > 2^15 ，方法 1 最快，執行時間約為方法 4 的一半。
當 n 接近 m 時，方法 1 的執行時間只有方法 2 的 1/30 。
結論
因為方法 4 本質上還是 recursion ，
所以可以把方法 4 的 base case 改成當 cn < m 時使用方法 1 ，
c 為一個小的正整數，這樣的話就可以讓方法 4 的速度永遠比方法 1 快了。
同理也可以把方法 2 放進去方法 4 的 base 中，得到一個速度永遠最快的方法。
[1] D. Woodhouse, "Programming the Josephus problem,"
ACM SIGCSE Bulletin, Volume 10 Issue 4, December 1978 Pages 56-58
[2] Fatih Gelgi's, "Time Improvement on Josephus Problem"
[3] Ronald L. Graham, Donald E. Knuth, Oren Patashnik
Concrete Mathematics, Section 3.3
[4] Donald E. Knuth
The Art of Computer Programming, Vol. 1: Fundamental Algorithms
Section 1.3.3 Exercise 31