【Algo】約瑟夫問題(Josephus problem / Josephus permutation)

Backto Algo Index

N N N 個人圍一圈, 選一個人, 從 1 開始計數, 計到第 k k k 個人出局, 剩下的人組成新環, 再次從 1 開始計數, 計到 k k k 的人出局. 如此反複, 直到剩下最後一個人, 作為勝利者. 問, 在遊戲開始時, 排在第幾号位置, 可以保證自己是最後的勝利者?

舉一個特例了解題目, 設 N = 6 , k = 5 N = 6, k = 5 N=6,k=5, 則這一圈人是

1	2	3	4	5	6	1	…

出局的順序依次是

5

->

4

->

6

->

2

->

3

, 是以開局時候排在第 1 1 1 位是勝利者.

程式設計求解的直接思路: 用一個 循環連結清單 儲存這 N N N 個人, data 裡存一個 bool 值, true 表示還在場上, false 表示出局. 然後循環周遊 N − 1 N - 1 N−1次, 最後剩下的人就是勝利者. But, 時間複雜度是 N × k N \times k N×k, 任何一個數非常大的話, 這個複雜度都是不可接受的.

優化, 重新分析問題, 試圖找到其中的隐含規律.

計算機語言問題描述： n n n 個人（編号 0 → ( n − 1 ） 0\to(n-1） 0→(n−1）），從 0 0 0開始報數，報到 （ m − 1 ） （m-1） （m−1）的退出，剩下的人繼續從 0 0 0 開始報數。求勝利者的編号。

我們可以确定, 第一個出列的人編号肯定是 ( m − 1 ) m o d    n (m-1) \mod n (m−1)modn, 那麼剩下的 n − 1 n-1 n−1 個人組成新的 約瑟夫環, 新環肯定以 ( k = m m o d    n k = m \mod n k=mmodn) 開始, 新環的排序肯定是 k , k + 1 , k + 2 , . . . , n − 2 , n − 1 , 0 , 1 , 2 , . . . , k − 2 k, k+1, k+2, ... , n-2, n-1, 0, 1, 2, ... , k - 2 k,k+1,k+2,...,n−2,n−1,0,1,2,...,k−2. 把這個新環的序号調整一下, 看做一個新的約瑟夫環

• k → 0 k \to 0 k→0
• k + 1 → 1 k+1 \to 1 k+1→1
• k + 2 → 2 k+2 \to 2 k+2→2
• . . . ... ...
• k − 2 → n − 2 k-2 \to n-2 k−2→n−2

也就是說變成了 n − 1 n-1 n−1 個人報數的子問題. 假設我們知道對于這個 n − 1 n-1 n−1個人的子問題, 第 x x x 個人是最終的勝利者, 那麼我們再把這個 x x x 塞回去就是剛好 n n n個人情況下的解了. 變回去的公式就是 x ′ = ( x + k ) m o d    n x' = (x+k) \mod n x′=(x+k)modn. 是以, 我們知道了 n − 1 n-1 n−1 下的解就可以求出 n n n 的解, 典型的遞歸問題.

const int n = 68; // total number
const int m = 3; // kill the m_th person
int f = 0; // safe position
int main()
{
    for (int i = 1; i <= n; i++) 
    	f = (f + m) % i;
    cout << f + 1 << endl; // counts from 1
}
           

時間複雜度 O ( n ) O(n) O(n), 空間複雜度 O ( 1 ) O(1) O(1), 好很多了.

Ref

• 約瑟夫問題 – 百度百科 : 問題的起源, 分析求解, 和不同版本語言實作. 想不到濃眉大眼的百度百科還要這麼優秀的詞條.
• 約瑟夫問題 : 語言實作寫的比較詳細完整