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

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 24.23.200.172 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1471117368.A.819.html ※ 编辑: FRAXIS (24.23.200.172), 08/16/2016 09:44:02