约瑟夫环问题的数学模型与递推证明
约瑟夫环（Josephus Problem）表面上是一个动态的模拟过程，但在数学本质上，它是一个纯粹的坐标映射与模运算（取余）问题。通过建立严格的数学模型，我们可以将问题的求解复杂度从逐个模拟的 \( O(n^2) \) 大幅降至 \( O(n) \)。
为了使取模运算连续且完美闭合，建立模型的第一步必须是打破常规的“1 到 n”编号习惯，将所有人的初始位置定义为 0 到 n-1。在接下来的所有推导过程中，我们将完全在 0 起始的坐标系中进行。
1. 变量定义
- 总人数： \( n \)
- 淘汰步长： \( k \)（即每次报数到 \( k \) 的人出列）
- 目标函数： \( f(n, k) \) 表示在 \( n \) 个人、步长为 \( k \) 的游戏中，最终存活者的位置编号（编号从 0 开始）。
2. 初始状态（边界条件）
当游戏中只有 1 个人时（\( n = 1 \)），无论步长 \( k \) 是多少，这个人永远不会被淘汰。由于我们的编号从 0 开始，此时他占据的唯一位置就是 0。
由此得到递推的基准值：
3. 核心推导：降维与坐标映射
假设现在有 \( n \) 个人排成一圈（编号 0 到 n-1）。
如果我们将剩下的这 \( n-1 \) 个人看作一场全新的游戏，并且重新从 0 开始给他们排定新编号，我们就把一个规模为 \( n \) 的问题，成功降维成了一个规模为 \( n-1 \) 的子问题。
我们需要建立“新游戏”与“旧游戏”之间的坐标映射关系：
| 新游戏编号 (规模 n-1) | 对应的旧游戏编号 (规模 n) |
|---|---|
| 0 | \( k \) |
| 1 | \( k + 1 \) |
| 2 | \( k + 2 \) |
| ...... | ...... |
| \( x \) | \( (x + k) \pmod n \) |
从表格中可以总结出一个极其规律的映射公式：旧坐标 = (新坐标 + k) 模 n。因为是环形结构，加上 \( k \) 之后如果超出了总人数 \( n \)，通过模运算（\(\pmod n\)）就能如同钟表指针一样，将坐标重新拨回合法的区间内。
4. 得出递推公式
假设我们已经求出了规模为 \( n-1 \) 时的幸存者位置，即 \( f(n-1, k) \)。这个位置是幸存者在“新游戏”里的编号。
为了知道他在最初“旧游戏”里到底坐在哪个位置，我们只需将他代入上面推导出的映射公式：将他的新编号加上偏移量 \( k \)，再对当前的圈子总人数 \( n \) 取模。
这就构成了约瑟夫环最核心的状态转移方程：
5. 实战演算：以 n=7, k=3 为例
为了更直观地理解上述公式，我们代入具体数值 \( n=7, k=3 \)。利用核心公式 \( f(n, 3) = (f(n-1, 3) + 3) \pmod n \)，我们可以从小到大逐步推导出最终存活者的位置（始终保持 0 起始）：
| 总人数 (n) | 递推计算过程 (0 起始) | 最终存活编号 f(n, 3) |
|---|---|---|
| n = 1 | 基准值 | 0 |
| n = 2 | (0 + 3) mod 2 | 1 |
| n = 3 | (1 + 3) mod 3 | 1 |
| n = 4 | (1 + 3) mod 4 | 0 |
| n = 5 | (0 + 3) mod 5 | 3 |
| n = 6 | (3 + 3) mod 6 | 0 |
| n = 7 | (0 + 3) mod 7 | 3 |
通过这张表格我们可以清楚地看到，当有 7 个人参与、每次报数到 3 淘汰时，最终存活下来的人坐在 3 号位置。
6. 补充说明：如何转换回常规的 1 到 n 编号？
在现实生活中，我们习惯从 1 开始报数（即编号为 1 到 \( n \)）。既然我们已经通过 0 起始的数学模型算出了极其优雅的结果，最后只需要做一个简单的坐标平移即可。
设日常 1 起始的最终存活函数为 \( J(n, k) \)。我们只需在算完 0 起始的结果后，整体加 1（平移回 1 起始）即可：
如果你想用一条公式直接表达包含转换过程的递推式，它长这样（即每次计算前先减 1 平移至 0 起始，算完取模后再加 1）：
在 \( n=7, k=3 \) 的计算中，我们得出 0 起始的最终存活者是 3 号。代入平移转换后，在日常的 1 到 7 的编号习惯中，最终存活的就是 4 号。