跳到主要内容

约瑟夫问题

约瑟夫问题由来已久，而这个问题的解法也在不断改进，只是目前仍没有一个极其高效的算法（log 以内）解决这个问题。

问题描述​

n 个人标号 0,1,⋯ ,n−10,1,\cdots, n-1。逆时针站一圈，从 00 号开始，每一次从当前的人逆时针数 kk 个，然后让这个人出局。问最后剩下的人是谁。

这个经典的问题由约瑟夫于公元 1 世纪提出，尽管他当时只考虑了 k=2k=2 的情况。现在我们可以用许多高效的算法解决这个问题。

过程​

朴素算法​

最朴素的算法莫过于直接枚举。用一个环形链表枚举删除的过程，重复 n−1n-1 次得到答案。复杂度 Θ(n2)\Theta (n^2)。

简单优化​

寻找下一个人的过程可以用线段树优化。具体地，开一个 0,1,⋯ ,n−10,1,\cdots, n-1 的线段树，然后记录区间内剩下的人的个数。寻找当前的人的位置以及之后的第 kk 个人可以在线段树上二分做。

线性算法​

设 Jn,kJ_{n,k} 表示规模分别为 n,kn,k 的约瑟夫问题的答案。我们有如下递归式

Jn,k=(Jn−1,k+k) mod nJ_{n,k}=(J_{n-1,k}+k)\bmod n

这个也很好推。你从 00 开始数 kk 个，让第 k−1k-1 个人出局后剩下 n−1n-1 个人，你计算出在 n−1n-1 个人中选的答案后，再加一个相对位移 kk 得到真正的答案。这个算法的复杂度显然是 Θ(n)\Theta (n) 的。

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

对数算法​

对于 kk 较小 nn 较大的情况，本题还有一种复杂度为 Θ(klog⁡n)\Theta (k\log n) 的算法。

考虑到我们每次走 kk 个删一个，那么在一圈以内我们可以删掉 ⌊nk⌋\left\lfloor\frac{n}{k}\right\rfloor 个，然后剩下了 n−⌊nk⌋n-\left\lfloor\frac{n}{k}\right\rfloor 个人。这时我们在第 ⌊nk⌋⋅k\left\lfloor\frac{n}{k}\right\rfloor\cdot k 个人的位置上。而你发现它等于 n−n mod kn-n\bmod k。于是我们继续递归处理，算完后还原它的相对位置。还原相对位置的依据是：每次做一次删除都会把数到的第 kk 个人删除，他们的编号被之后的人逐个继承，也即用 n−⌊nk⌋n-\left\lfloor\frac{n}{k}\right\rfloor 人环算时每 kk 个人即有 11 个人的位置失算，因此在得数小于 00 时，用还没有被删去 kk 倍数编号的 nn 人环的 的 nn 求模，在得数大于等于 00 时，即可以直接乘 kk−1\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;
}

可以证明这个算法的复杂度是 Θ(klog⁡n)\Theta (k\log n) 的。我们设这个过程的递归次数是 xx，那么每一次问题规模会大致变成 n(1−1k)\displaystyle n\left(1-\frac{1}{k}\right)，于是得到

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

解这个方程得到

x=−ln⁡nln⁡(1−1k)x=-\frac{\ln n}{\ln\left(1-\frac{1}{k}\right)}

下面我们证明该算法的复杂度是 Θ(klog⁡n)\Theta (k\log n) 的。

证明

考虑 lim⁡k→∞klog⁡(1−1k)\displaystyle \lim _{k \rightarrow \infty} k \log \left(1-\frac{1}{k}\right)，我们有

lim⁡k→∞klog⁡(1−1k)=lim⁡k→∞log⁡(1−1k)1/k=lim⁡k→∞ddklog⁡(1−1k)ddk(1k)=lim⁡k→∞1k2(1−1k)−1k2=lim⁡k→∞−kk−1=−lim⁡k→∞11−1k=−1\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∼kln⁡n,k→∞x \sim k \ln n, k\to \infty，即 −ln⁡nln⁡(1−1k)=Θ(klog⁡n)-\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。

中等 (500)