[心得] Josephus Problem

[FRAXIS (喔喔)]

Josephus Problem是蠻常見的題目，像是ACM上面就有很多變形題，

我整理了一些解法跟大家分享。


假設有n個人為成一圈，並且依序編號為1 ~ n，從一號開始數，每

數m個人就把此人由圈圈中刪除，一直持續此動作直到只剩下一個人

為止才終止。

最簡單的題目是要計算出最後一個人的編號，有很多種解法。

第一種是用Queue來模擬此問題，也是最常見的解法，需要花時間O( nm )。

第二種方法是，假設上一輪刪除的是在剩餘人中編號第k大的人，

那麼下一輪被刪除的就會是編號第k + m - 1大的人，如果有一個

資料結構可以提供插入、刪除、找第k大等操作，就可以解決此問

題。而平衡二元樹就可以支援這些運算，需要花時間O( nlg n )。

第三種方法是由題目找出遞迴關係式

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

由此遞迴關係式可以直接寫成程式，需要花時間O( n )。

return n == 1 ? 1 : (f( n-1, m ) + m - 1) % n + 1;

如果是要找第k個被刪除的號碼

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

程式碼

return k == 0 ? 0 : (f(n-1, m, k - 1) + m - 1) % n + 1;

改成迴圈版本可以省去遞回所使用的堆疊空間。

for ( answer = 1, i = 2; i <= n; ++i )
    answer = (answer + m - 1) % i + 1;

找第k個被刪除的號碼

for ( answer = 0, i = n - k + 1; i <= n; ++i )
    answer = ( answer + m - 1 ) % i + 1;

第四種方法是另外一種遞迴式，用queue模擬需要mn步，想像成

mn個人排成一排，要算出最後一個人的號碼。

迴圈版本

for ( answer = m * n; answer > n; )
    answer = answer - n + (answer - n - 1)/(m-1);

這方法需要花O( m )的時間

如果要找第k個被刪除的號碼

for ( answer = k * m; answer > n; )
    answer = answer - n + (answer - n - 1)/(m-1);

第五種方法是另外一種遞迴關係式，第三種方法的遞迴關係一次

只會刪除一個人，但是實際上當m << n的時候，可以一次刪除很

多人。

g(n, m) = if n <= m -> f( m, m )
          if g(n -floor(n/m), m ) <= n % m
             -> g(n - floor(n/m), m) + floor(n/m)*m
          if g(n -floor(n/m), m ) > n % m
             if          (g(n - floor(n/m), m) - n % q) % (q-1) = 0
                -> floor((g(n - floor(n/m), m) - n % q) / (q-1)) * q - 1
             if          (g(n - floor(n/m), m) - n % q) % (q-1) != 0
                -> floor((g(n - floor(n/m), m) - n % q) / (q-1)) * q
                       + (g(n - floor(n/m), m) - n % q) % (q-1)

遞迴的程式碼如下
if ( n <= m )
    return f( n, m ); //利用第六種解法輔助
jn = g( n - n/m, m );
if ( jn <= n % m )
    return jn + (n/m) * m;
jn -= n % m;
return (jn / (m-1)) * m +
       (jn % (m-1) == 0 ?
        -1 :
        jn % (m-1));

這方法要花O( log m )的時間。

找第k個被刪除的也可以用類似的方法，至於轉換成迴圈應該也是可

能的，只是我找不出來，如果有人找的出來請告訴我。

第六種方法類似第四種方法，只是推導的方向不同。

for ( D = 1; D <= (m-1) * n; )
    D = (m * D)/(m-1) + ((m * D) % (m-1) != 0);
return m * n + 1 - D;

要花O( log n + log m )的時間。

至於怎麼改成找出第k個被刪除的號碼我就不知道了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51
推 stopcrying:how about change 1~n to 0~n-1 and add 1 after
→ stopcrying:you found the answer?
推 seanwu:第四個方法的複雜度不大對，每次最多-n，所以至少是O(m)吧?
推 DJWS:想請教一下第四種方法的原理...看不懂  @@"
→ FRAXIS:謝謝二樓 我修正了複雜度關係 並且加上第六種方法
→ FRAXIS:至於第四種方法的原理我也不知道
→ FRAXIS:http://www.cs.man.ac.uk/~shamsbaa/  這是原作者網頁
→ FRAXIS:網頁上說他的結果被加入The Art of Computer Programming中
※ 編輯: FRAXIS          來自: 140.119.162.51       (07/14 13:12)
推 seanwu:第四種方法我猜它的意思是說，queue中第ans'個的位置，
→ seanwu:該位置的值，會等於第ans個的值
→ seanwu:那麼當ans<n時，這時queue裡面該位置的值就是一開始的那圈
→ seanwu:之中的位置，就是說queue中第n*m個的值會等於ans(+1)