PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[心得] Josephus problem

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間8年前 (2016/08/14 03:42)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/1

幾年前我在 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://www.ptt.cc/bbs/Prob_Solve/M.1471117368.A.819.html ※ 編輯: FRAXIS (24.23.200.172), 08/16/2016 09:44:02