约瑟夫问题

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，处刑下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。

问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

朴素算法

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

线性算法

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

$$J_{n,k} = J_{n-1,k} \mod n$$

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

1
2
3
4
5

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

对数算法

对于 k 较小 n 较大的情况，本题还有一种复杂度为 $O(klogn)$ 的算法。

考虑到我们每次走 k 个删一个，那么在一圈以内我们可以删掉 ${n \over k}$ 个，然后剩下了 $n-{n \over k}$ 个人。这时我们在第 ${n \over k}\cdot k$ 个人的位置上。而你发现这个东西它等于 $n-n \mod k$ 。于是我们继续递归处理，算完后还原它的相对位置。得到如下的算法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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;
}

https://cp-algorithms.com/others/josephus_problem.html