約瑟夫問題

約瑟夫問題由來已久，而這個問題的解法也在不斷改進，只是目前仍沒有一個極其高效的算法（log 以內）解決這個問題。

問題描述

n 個人標號 \(0,1,\cdots, n-1\)。逆時針站一圈，從 \(0\) 號開始，每一次從當前的人逆時針數 \(k\) 個，然後讓這個人出局。問最後剩下的人是誰。

這個經典的問題由約瑟夫於公元 1 世紀提出，儘管他當時只考慮了 \(k=2\) 的情況。現在我們可以用許多高效的算法解決這個問題。

過程

樸素算法

最樸素的算法莫過於直接枚舉。用一個環形鏈表枚舉刪除的過程，重複 \(n-1\) 次得到答案。複雜度 \(\Theta (n^2)\)。

簡單優化

尋找下一個人的過程可以用線段樹優化。具體地，開一個 \(0,1,\cdots, n-1\) 的線段樹，然後記錄區間內剩下的人的個數。尋找當前的人的位置以及之後的第 \(k\) 個人可以在線段樹上二分做。

線性算法

設 \(J_{n,k}\) 表示規模分別為 \(n,k\) 的約瑟夫問題的答案。我們有如下遞歸式

\[ J_{n,k}=(J_{n-1,k}+k)\bmod n \]

這個也很好推。你從 \(0\) 開始數 \(k\) 個，讓第 \(k-1\) 個人出局後剩下 \(n-1\) 個人，你計算出在 \(n-1\) 個人中選的答案後，再加一個相對位移 \(k\) 得到真正的答案。這個算法的複雜度顯然是 \(\Theta (n)\) 的。

實現

int josephus(int n, int k) {
  int res = 0;
  for (int i = 1; i <= n; ++i) res = (res + k) % i;
  return res;
}

對數算法

對於 \(k\) 較小 \(n\) 較大的情況，本題還有一種複雜度為 \(\Theta (k\log n)\) 的算法。

考慮到我們每次走 \(k\) 個刪一個，那麼在一圈以內我們可以刪掉 \(\left\lfloor\frac{n}{k}\right\rfloor\) 個，然後剩下了 \(n-\left\lfloor\frac{n}{k}\right\rfloor\) 個人。這時我們在第 \(\left\lfloor\frac{n}{k}\right\rfloor\cdot k\) 個人的位置上。而你發現它等於 \(n-n\bmod k\)。於是我們繼續遞歸處理，算完後還原它的相對位置。還原相對位置的依據是：每次做一次刪除都會把數到的第 \(k\) 個人刪除，他們的編號被之後的人逐個繼承，也即用 \(n-\left\lfloor\frac{n}{k}\right\rfloor\) 人環算時每 \(k\) 個人即有 \(1\) 個人的位置失算，因此在得數小於 \(0\) 時，用還沒有被刪去 \(k\) 倍數編號的 \(n\) 人環的的 \(n\) 求模，在得數大於等於 \(0\) 時，即可以直接乘 \(\frac{k}{k-1}\), 於是得到如下的算法：

實現

int josephus(int n, int k) {
  if (n == 1) return 0;
  if (k == 1) return n - 1;
  if (k > n) return (josephus(n - 1, k) + k) % n;  // 線性算法
  int res = josephus(n - n / k, k);
  res -= n % k;
  if (res < 0)
    res += n;  // mod n
  else
    res += res / (k - 1);  // 還原位置
  return res;
}

可以證明這個算法的複雜度是 \(\Theta (k\log n)\) 的。我們設這個過程的遞歸次數是 \(x\)，那麼每一次問題規模會大致變成 \(\displaystyle n\left(1-\frac{1}{k}\right)\)，於是得到

\[ n\left(1-\frac{1}{k}\right)^x=1 \]

解這個方程得到

\[ x=-\frac{\ln n}{\ln\left(1-\frac{1}{k}\right)} \]

下面我們證明該算法的複雜度是 \(\Theta (k\log n)\) 的。

證明

考慮 \(\displaystyle \lim _{k \rightarrow \infty} k \log \left(1-\frac{1}{k}\right)\)，我們有

\[ \begin{aligned} \lim _{k \rightarrow \infty} k \log \left(1-\frac{1}{k}\right)&=\lim _{k \rightarrow \infty} \frac{\log \left(1-\frac{1}{k}\right)}{1 / k}\\ &=\lim _{k \rightarrow \infty} \frac{\frac{\mathrm d}{\mathrm d k} \log \left(1-\frac{1}{k}\right)}{\frac{\mathrm d}{\mathrm d k}\left(\frac{1}{k}\right)}\\ &=\lim _{k \rightarrow \infty} \frac{\frac{1}{k^{2}\left(1-\frac{1}{k}\right)}}{-\frac{1}{k^{2}}}\\ &=\lim _{k \rightarrow \infty}-\frac{k}{k-1}\\ &=-\lim _{k \rightarrow \infty} \frac{1}{1-\frac{1}{k}}\\ &=-1 \end{aligned} \]

所以 \(x \sim k \ln n, k\to \infty\)，即 \(-\dfrac{\ln n}{\ln\left(1-\frac{1}{k}\right)}= \Theta (k\log n)\)

本頁面主要譯自博文 Задача Иосифа 與其英文翻譯版 Josephus Problem。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用