跳转至

# 约瑟夫问题

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

## 问题描述

> n 个人标号 0,1,⋯,𝑛 −1 0,1,⋯,n−1．逆时针站一圈，从 0 0 号开始，每一次从当前的人逆时针数 𝑘 k 个，然后让这个人出局．问最后剩下的人是谁．

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

## 过程

### 朴素算法

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

### 简单优化

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

### 线性算法

设 𝐽 𝑛,𝑘 J n,k 表示规模分别为 𝑛,𝑘 n,k 的约瑟夫问题的答案．我们有如下递归式

𝐽 𝑛,𝑘=(𝐽 𝑛−1,𝑘+𝑘)m o d 𝑛 J n,k=(J n−1,k+k)mod n

这个也很好推．你从 0 0 开始数 𝑘 k 个，让第 𝑘 −1 k−1 个人出局后剩下 𝑛 −1 n−1 个人，你计算出在 𝑛 −1 n−1 个人中选的答案后，再加一个相对位移 𝑘 k 得到真正的答案．这个算法的复杂度显然是 Θ(𝑛)Θ(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 较大的情况，本题还有一种复杂度为 Θ(𝑘 l o g⁡𝑛)Θ(k log⁡n) 的算法．

考虑到我们每次走 𝑘 k 个删一个，那么在一圈以内我们可以删掉 ⌊𝑛 𝑘⌋⌊n k⌋ 个，然后剩下了 𝑛 −⌊𝑛 𝑘⌋n−⌊n k⌋ 个人．这时我们在第 ⌊𝑛 𝑘⌋ ⋅𝑘⌊n k⌋⋅k 个人的位置上．而你发现它等于 𝑛 −𝑛 m o d 𝑘 n−n mod k．于是我们继续递归处理，算完后还原它的相对位置．还原相对位置的依据是：每次做一次删除都会把数到的第 𝑘 k 个人删除，他们的编号被之后的人逐个继承，也即用 𝑛 −⌊𝑛 𝑘⌋n−⌊n k⌋ 人环算时每 𝑘 k 个人即有 1 1 个人的位置失算，因此在得数小于 0 0 时，用还没有被删去 𝑘 k 倍数编号的 𝑛 n 人环的 的 𝑛 n 求模，在得数大于等于 0 0 时，即可以直接乘 𝑘 𝑘−1 k k−1, 于是得到如下的算法：

实现

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

可以证明这个算法的复杂度是 Θ(𝑘 l o g⁡𝑛)Θ(k log⁡n) 的．我们设这个过程的递归次数是 𝑥 x，那么每一次问题规模会大致变成 𝑛(1−1 𝑘)n(1−1 k)，于是得到

𝑛(1−1 𝑘)𝑥=1 n(1−1 k)x=1

解这个方程得到

𝑥=−l n⁡𝑛 l n⁡(1−1 𝑘)x=−ln⁡n ln⁡(1−1 k)

下面我们证明该算法的复杂度是 Θ(𝑘 l o g⁡𝑛)Θ(k log⁡n) 的．

证明

考虑 l i m 𝑘→∞𝑘 l o g⁡(1−1 𝑘)lim k→∞k log⁡(1−1 k)，我们有

l i m 𝑘→∞𝑘 l o g⁡(1−1 𝑘)=l i m 𝑘→∞l o g⁡(1−1 𝑘)1/𝑘=l i m 𝑘→∞d d 𝑘 l o g⁡(1−1 𝑘)d d 𝑘(1 𝑘)=l i m 𝑘→∞1 𝑘 2(1−1 𝑘)−1 𝑘 2=l i m 𝑘→∞−𝑘 𝑘−1=−l i m 𝑘→∞1 1−1 𝑘=−1 lim k→∞k log⁡(1−1 k)=lim k→∞log⁡(1−1 k)1/k=lim k→∞d d k log⁡(1−1 k)d d k(1 k)=lim k→∞1 k 2(1−1 k)−1 k 2=lim k→∞−k k−1=−lim k→∞1 1−1 k=−1

所以 𝑥 ∼𝑘 l n⁡𝑛,𝑘 →∞x∼k ln⁡n,k→∞，即 −l n⁡𝑛 l n⁡(1−1 𝑘) =Θ(𝑘 l o g⁡𝑛)−ln⁡n ln⁡(1−1 k)=Θ(k log⁡n)

本页面主要译自博文 Задача Иосифа 与其英文翻译版 Josephus Problem．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Enter-tainer, sshwy, F1shAndCat, FFjet, iamtwz, Ir1d, Tiphereth-A
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用