几年前我在 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