[心得] Josephus Problem

看板C_and_CPP (C/C++)作者FRAXIS (喔喔)時間16年前 (2009/07/13 22:35)推噓4(4推 0噓 8→)

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

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