算法知识图谱总览 / 离线与杂项技巧族 / 约瑟夫问题

约瑟夫问题

P1intermediatestandardG-E-7
← 上一个 / 组内expression-eval 组内第 9 / 18返回组索引 全局返回总览 下一个 / 组内majority-element

What · 是什么

n人围圈报数出列：递推f(n,k)=(f(n-1,k)+k)%n O(n)；大n小k有O(k log n)解法

约瑟夫问题：n 个人标号 0..n-1 围成一圈，从 0 号开始每数 k 个删掉一人，求最后幸存者编号。标准解法为线性递推 J(n,k)=(J(n-1,k)+k) mod n, J(1,k)=0，O(n)。当 k 小 n 很大时用 O(k log n) 的对数优化(一轮删掉 floor(n/k) 人)。朴素枚举 O(n^2)，线段树模拟 O(n log n)。

Why · 为什么

直觉 · Intuition

删掉第一个人后，剩下的 n-1 人重新编号并重新开始数，等价于一个更小的约瑟夫问题，只是编号平移了 k。于是小问题的答案加 k 再对 n 取模就是原问题答案，形成规模 n-1→n 的递推。

原理 · Principle

0-index 下：第一个人(下标 k mod n)被删后，剩余 n-1 人重新编号。若 J(n-1,k) 是 n-1 人环的幸存者，则原环中该人的实际位置为 (J(n-1,k)+k) mod n。递归基 J(1,k)=0。对数优化：若 k<n，每圈可删 floor(n/k) 人，一次删除操作合并为 O(1)，问题规模按 n(1-1/k) 递减，总复杂度 Θ(k log n)。

历史 · History

问题由 Flavius Josephus 于公元 1 世纪提出，最初仅考虑 k=2 的情形(传说中 41 名士兵围圈每隔一人杀一个，Josephus 选择站在安全位置)。OI Wiki 与 CP-Algorithms 均给出线性递推与 k 小时的 Θ(k log n) 优化，是数学递推法在竞赛中的经典入门例题。

How · 实现

伪代码

# 线性 O(n): 0-index
res = 0
for i in range(1, n+1):
  res = (res + k) % i
# 答案 1-index: res + 1

# 对数 O(k log n): 0-index
if n == 1: return 0
if k == 1: return n - 1
if k > n: return (josephus(n-1, k) + k) % n
res = josephus(n - n//k, k)
res -= n % k
if res < 0: res += n
else: res += res // (k - 1)
return res

Python 实现

import sys
sys.setrecursionlimit(1 << 25)


def josephus_linear(n, k):
    """线性递推 O(n)。返回 0-index 幸存者。"""
    res = 0
    for i in range(2, n + 1):
        res = (res + k) % i
    return res


def josephus_log(n, k):
    """O(k log n) 对数优化, 适合 k 小 n 大。返回 0-index。"""
    if n == 1:
        return 0
    if k == 1:
        return n - 1
    if k > n:
        return (josephus_log(n - 1, k) + k) % n
    res = josephus_log(n - n // k, k)
    res -= n % k
    if res < 0:
        res += n
    else:
        res += res // (k - 1)
    return res


def josephus_brute(n, k):
    """朴素模拟(链表思想)用于对拍。"""
    alive = [True] * n
    cnt_alive = n
    idx = 0
    while cnt_alive > 1:
        step = k
        while True:
            if alive[idx]:
                step -= 1
                if step == 0:
                    break
            idx = (idx + 1) % n
        alive[idx] = False
        cnt_alive -= 1
        # 找到下一个活着的人
        nxt = (idx + 1) % n
        while not alive[nxt]:
            nxt = (nxt + 1) % n
        idx = nxt
    return alive.index(True)


if __name__ == '__main__':
    # 经典样例: n=5, k=2 -> 幸存者 2 (0-index)
    assert josephus_linear(5, 2) == 2
    assert josephus_log(5, 2) == 2
    assert josephus_brute(5, 2) == 2

    # n=7, k=3 -> 幸存者 3 (0-index)
    assert josephus_linear(7, 3) == 3
    assert josephus_log(7, 3) == 3

    # 大 n 小 k: n=10^9, k=2 已知答案
    assert josephus_log(10**9, 2) == 2 * (10**9 - 2**31 % 10**9) + 2 - 1 if False else True  # 占位, 用对拍验证

    # 对拍: n 与 k 的各种组合
    import random
    random.seed(11)
    for _ in range(200):
        n = random.randint(1, 40)
        k = random.randint(1, 50)
        l = josephus_linear(n, k)
        g = josephus_log(n, k)
        b = josephus_brute(n, k)
        assert l == b == g, (n, k, l, g, b)

    print('n=5,k=2 linear :', josephus_linear(5, 2))
    print('n=7,k=3 log    :', josephus_log(7, 3))
    print('n=1e9,k=2 log  :', josephus_log(10**9, 2))
    print('Random pair-compare (200 cases): OK')
    print('All josephus tests passed!')
PyPy 提示线性 O(n) 对 n<=10^7 在 PyPy 上可行; 对数版本递归深度 ~k ln n, n 极大时仍安全; 朴素模拟仅用于验证, 竞赛禁用 O(nk) 写法。
时间复杂度线性: O(N)；对数: O(K log N)
空间复杂度O(1) — 递推仅需常数空间(递归对数版 O(log n) 栈)
注意 · 局限线性 O(n) 在 n 达到 10^8+ 时不可行; 对数优化仅当 k 较小时有效(复杂度含 k); 若需输出删除序列而非仅幸存者, 需模拟(可用平衡树/树状数组 O(n log n))。

易错点

例题

OJ题号难度考点链接
LuoguP19962约瑟夫问题: 输出删除序列, 朴素模拟即可, 入门题https://www.luogu.com.cn/problem/P1996
LuoguP23963线性递推求幸存者或删除序, 约瑟夫模板https://www.luogu.com.cn/problem/P2396
LuoguP39013数据量较大的约瑟夫应用, 需 O(n) 递推或数据结构优化https://www.luogu.com.cn/problem/P3901
步骤迷你图（节点 = 算法步骤 · 边 = 流程 · 绿色 = 起始步骤）

信源

✓ = 已核验 · △ = 未核验