约瑟夫环

题目描述

$n$ 个人围成一圈，编号为1到 $n$。从1号开始报数，数到 $k$ 的人出局；下一人重新从1报数，直到只剩一个人。求最后幸存者的原始编号。约定 $n$ 和 $k$ 都是正整数。

例如 $n=7,k=3$ 时：

轮次	开始报数的人	出局者	下一轮开始报数的人
1	1	3	4
2	4	6	7
3	7	2	4
4	4	7	1
5	1	5	1
6	1	1	4

出局顺序是3、6、2、7、5、1，最后留下4号。逐个删除可以求解，但如果只要求幸存者，就可以利用更小圆环的答案。

报数从1开始，每次出局后，下一个仍在圈内的人重新报1；出局者不再参与后续报数。只剩1人时立即结束，不再把最后一个人删除。

题目分析

缩小问题并重新编号

第一次出局之后，还有 $n-1$ 个人，报数规则不变。这就是一个规模更小的约瑟夫环。不过它的报数起点变了，所以小环得到的编号必须转换回原来的编号。

为使转换公式简单，函数内部使用0到 $n-1$ 的编号。原题中的1号对应内部0号，原题中的3号对应内部2号，最终输出时再加1。

在内部编号下，从0开始报数，首次出局者是 $(k-1)\bmod n$，下一轮起点是 $k\bmod n$。把这个起点重新编号为0，沿圆环为其他幸存者编号。

以 $n=7,k=3$ 为例，原题3号出局后的映射为：

原题编号	原来的内部编号	小环的新内部编号
4	3	0
5	4	1
6	5	2
7	6	3
1	0	4
2	1	5

如果子问题告诉我们幸存者在新编号中是 $x$，其原来的内部编号就是：

$$(x+k)\bmod n.$$

加 $k$ 是恢复原来的起点偏移，取余是处理绕过圆环末尾的情况。偏移量是报数间隔 $k$，不是被删除人数1，也不是圆环人数 $n$。

建立递归公式

令 $f(n,k)$ 表示人数为 $n$、报数间隔为 $k$ 时，幸存者从0开始的内部编号。于是：

$$f(n,k)= \begin{cases} 0, & n=1,\\ \bigl(f(n-1,k)+k\bigr)\bmod n, & n>1. \end{cases}$$

终止条件是只剩一个人，其内部编号一定为0。每次调用让人数减1，最终会到达这个条件。子问题返回的是重新编号后的位置，当前层负责把它映射回自己的圆环。

这里用公式直接计算最后的幸存者；它不保存报数过程或完整的出局顺序。理解公式时，应把“小环重新编号”与“原题固定编号”区分开。

实现代码

Python 递归实现

对外函数返回原题中从1开始的编号；内部函数始终使用从0开始的编号，避免在每一层混用两种编号。

def josephus(n, k):
    """返回幸存者从1开始的原始编号。"""
    if n < 1 or k < 1:
        raise ValueError("n 和 k 必须是正整数")

    def survivor(size):
        """返回当前圆环中从0开始的幸存者编号。"""
        if size == 1:
            return 0

        smaller = survivor(size - 1)  # 小环的幸存者位置
        return (smaller + k) % size   # 映射回当前圆环

    return survivor(n) + 1           # 只在最终输出前加1


print("幸存者编号：", josephus(7, 3))

输出：

幸存者编号： 4

Python 循环实现

从人数1的答案开始，依次求人数2、3直到 $n$ 的幸存者位置：

def josephus_iterative(n, k):
    if n < 1 or k < 1:
        raise ValueError("n 和 k 必须是正整数")

    result = 0
    for size in range(2, n + 1):
        result = (result + k) % size
    return result + 1


print(josephus_iterative(7, 3))  # 4

循环版本时间复杂度为 $O(n)$，辅助空间为 $O(1)$。它正好按递归返回时的顺序计算各层答案，不需要把等待状态放入递归栈。

Python 模拟实现：输出出局顺序

如果还需要知道每一轮谁出局，可以维护一个存放原始编号的列表。index 指向本轮开始报数的人，他报的是1，因此数到 $k$ 的位置要前进 k - 1 个位置。

def josephus_simulate(n, k):
    """返回出局顺序和幸存者，均使用从1开始的原始编号。"""
    if n < 1 or k < 1:
        raise ValueError("n 和 k 必须是正整数")

    people = list(range(1, n + 1))
    eliminated = []
    index = 0

    while len(people) > 1:
        index = (index + k - 1) % len(people)
        eliminated.append(people.pop(index))
        # 删除后，后一个人移到相同的列表位置。
        # 若删除的是末尾，下次取余会自动回到列表开头。

    return eliminated, people[0]


order, survivor = josephus_simulate(7, 3)
print("出局顺序：", order)
print("幸存者编号：", survivor)

输出：

出局顺序： [3, 6, 2, 7, 5, 1]
幸存者编号： 4

三段代码中的参数都约定为正整数。对于只求幸存者的大规模输入，优先使用循环公式；列表模拟适合展示报数和出局过程。

算法执行过程

交互动画

动画默认使用 $n=7,k=3$。点击“下一步”逐个报数，数到 $k$ 的人出局；点击“上一步”可以回看，修改人数或报数间隔后点击“应用”重新开始。课堂展示时可切换全屏。

先对齐编号

正文的人员编号为1到 $n$，动画的初始编号为0到 $n-1$，因此动画中的幸存者编号加1，才是题目中的答案。例如动画最终显示初始编号3，对应题目中的4号。

深色数字是固定的初始编号，蓝色标签是当前圆环重新编号后的位置。每次淘汰之后才重新编号，报数中途保持不变。递推公式 $(x+k)\bmod n$ 恢复的是上一层圆环的局部编号；经过多次淘汰后，要逐层映射，不能直接对初始总人数取余。

修改参数后点击“应用”，使用上一步和下一步观察过程。

报数与出局

以 $n=7,k=3$ 为例，第1轮从1号开始，1号报1、2号报2、3号报3，3号出局；第2轮从4号重新开始，4号报1、5号报2、6号报3，6号出局。

之后重复相同规则，按照题目描述中的表格依次删除2、7、5、1，最后剩下4号。整个模拟过程中，人的原始编号保持不变。

递归调用与返回

递归向下依次求人数7、6、5直到1的子问题，返回时依次计算：

人数 $n$	幸存者内部编号 $f(n,3)$	计算过程
1	0	终止条件
2	1	$(0+3)\bmod2$
3	1	$(1+3)\bmod3$
4	0	$(1+3)\bmod4$
5	3	$(0+3)\bmod5$
6	0	$(3+3)\bmod6$
7	3	$(0+3)\bmod7$

最后内部编号为3，对应原题编号4。表格每一行描述的是不同大小圆环各自的幸存者位置，不是同一个人在模拟过程中不断改变自己的原始编号。

循环公式与递归返回阶段的计算顺序一致。这个表格展示的是“由小问题构造大问题的答案”，报数出局展示的是“不断删除人的实际过程”，两者最终都得到4号幸存。

复杂度分析

采用基本操作计数模型，把一次整数加法、取余等算术操作视为常数时间，辅助空间按变量和栈帧数量计算。每层只调用一次人数减1的子问题，有：

$$T(n)=T(n-1)+O(1),\qquad T(1)=O(1).$$

展开可知，共有 $n$ 层、每层常数工作量，所以时间复杂度为 $O(n)$。最大调用深度为 $n$，辅助空间复杂度为 $O(n)$。这一结论针对公式求幸存者，不是逐个删除列表的模拟算法。

实现方式	时间复杂度	辅助空间复杂度	是否输出出局顺序
递归公式	$O(n)$	$O(n)$	否
循环公式	$O(n)$	$O(1)$	否
Python 列表模拟	$O(n^2)$，最坏情况	$O(n)$	是

列表模拟使用 pop(index) 删除元素，后续元素可能需要整体前移。虽然只删除 $n-1$ 次，最坏情况下仍需 $O(n^2)$ 时间。上述结论把整数加法与取余等基本操作按常数时间计数。

易错点

易错点	正确理解
将内部编号和原题编号混用	公式内部从0开始，最终结果只加1一次
将公式偏移写成 k - 1	编号映射公式加 $k$；列表找出局位置才加 $k-1$
出局后从原来的起点重新报数	从出局者后面仍在圈内的人重新报1
认为 $k$ 不能超过人数	$k$ 可大于人数，取余处理多次绕圈
把递推表当成同一个人的编号变化	每一行表示不同大小圆环各自的答案

当 $n=1$ 时，幸存者为1号，出局顺序为空。当 $k=1$ 时，每次报1的人立即出局，最终幸存者为 $n$ 号。递归深度受 Python 运行环境限制，人数较多时应使用循环公式。

课堂练习

1. 求 $n=5,k=2$ 的出局顺序和幸存者，并用循环公式核对。
2. 解释为什么小环结果映射回大环时加 $k$，而列表模拟找出局者时加 $k-1$。
3. 求 $n=4,k=7$ 的幸存者，观察报数间隔超过人数时取余的作用。

参考答案

1. 出局顺序为2、4、1、5，幸存者为3号。
2. 小环起点是首次出局者的下一人，其原内部编号为 $k\bmod n$；模拟从当前人报1，走到报 $k$ 的人只需前进 $k-1$ 个位置。
3. 出局顺序为3、4、1，幸存者为2号。

相关学习：递归方法实例、递归与分治。