洛谷 P1996 约瑟夫问题 —— 递归与线性模拟解法

1. 题目背景与描述

题目来源：洛谷 P1996 约瑟夫问题

$n$ 个人围成一圈，从第一个人开始报数，数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依此类推，直到所有人都出圈。请输出依次出圈人的编号。

输入格式

输入两个整数 $n, m$。

输出格式

输出一行 $n$ 个整数，按顺序输出每个出圈人的编号，以空格隔开。

输入输出样例 #1

输入：

10 3

输出：

3 6 9 2 7 1 8 5 10 4

数据范围

$1 \le m, n \le 100$

---

2. 问题剖析与解题思路

本题数据规模较小（$n \le 100$），全流程模拟即可轻松通过。而在各种模拟方式中，基于动态数组（std::vector）的递归写法结构精炼，非常契合这道题的递归子结构。

2.1 递归的三大要素

1. 子问题定义：
   • 原问题：当前圈内有 $k$ 个人，从某个起始下标开始数到 $m$ 的人出圈。
   • 子问题：某人出圈后，圈内剩下 $k - 1$ 个人，从其下一个人重新开始数到 $m$ 出圈。
   • 规律：问题规模在逐步缩小（$k \to k - 1$），但出圈与报数规则完全一致，符合标准的递归子结构。
2. 递归终止条件：
   • 当圈内人数减为 0（即 $n = 0$）时，所有人均已出圈，递归直接返回。
3. 数据结构选择：
   • 常见解法包括循环链表、队列（std::queue）、动态数组（std::vector）。
   • 考虑到 $n \le 100$，手写链表代码量偏多，而 std::vector 自带连续存储与元素删除平移能力，用它来实现逻辑最为紧凑。

---

3. 核心难点与数学推导

核心一：如何计算本轮出圈人的下标？

我们采用 0-indexed（从 0 开始编号） 的连续线性空间来维护圈中幸存的人：

• 假设当前圈内剩余 $k$ 个人，下标分别为 $0, 1, \dots, k-1$。
• 假设本轮报数从下标 start 开始：
  • 自己报 1 $\implies$ 相对偏移量为 $0$
  • 下一人报 2 $\implies$ 相对偏移量为 $1$
  • $\dots$
  • 报到 $m$ 的人 $\implies$ 相对偏移量为 $m - 1$

由于队伍首尾相连成环，当累加超出数组末尾时需循环回头部。因此出圈人的绝对下标为：

$$\text{target} = (\text{start} + m - 1) \bmod k$$

注意：此处务必模上当前人数 $k$，否则连续累加会导致数组越界。

---

核心二：元素删除后，下一轮的报数起始点在哪里？

这是本解法最巧妙、最易产生直觉误区的地方：

假设当前数组有 5 人：[A, B, C, D, E]，下标分别为 0, 1, 2, 3, 4。

• 假设本轮计算出 target = 2（即 C 出圈）。
• 将 C 删除后，C 后面的元素 D, E 会整体向左平移 1 位，填补空缺：
  • 原来下标 3 的 D $\to$ 变成了下标 2
  • 原来下标 4 的 E $\to$ 变成了下标 3
• 按照规则，下一轮报数应当从 C 的下一个人（即 D）开始。
• 此时你会发现：D 当前所在的新下标，恰好就是被删掉的 target（2）！

结论：
当把当前出圈元素删除并整体左移后，下一轮递归的起始下标 start 直接传入 target 即可。

特例验证：如果删除的是末尾元素（例如原最后一人），左移后数组长度缩小为 $k-1$，$target = k-1$ 超出了新边界吗？
下一轮进入函数时，会再次执行 $(\text{start} + m - 1) \bmod (k-1)$，通过取模自动绕回下标 0，逻辑依然自洽！

---

核心三：如何完成元素的整体平移与删除？

主要有两种代码实现风格：

方式 1：利用 std::vector::erase（推荐，代码极简）

a.erase(a.begin() + target);

• a.begin() 返回指向首元素的迭代器，加上 target 即可定位到目标元素。
• erase() 会自动析构该元素，并将其后所有元素向左移动一格，同时容器大小自动减 1。
• 缺点是每次移动复杂度为 $O(k)$，但在 $n \le 100$ 的数据规模下耗时不足 1 毫秒，体验最好。

方式 2：使用原生数组 for 循环左移

for (int i = target; i < k - 1; ++i) {
    a[i] = a[i + 1];
}

手动用后项覆盖前项，有效长度减 1。逻辑透明，不依赖 STL 容器。

---

4. 完整代码实现

#include <iostream>
#include <vector>

/**
 * 递归模拟约瑟夫环出圈过程
 * @param a     当前在圈内的成员列表
 * @param n     当前剩余人数
 * @param m     每次报数的上限
 * @param start 本轮开始报数的成员下标
 */
void josephus(std::vector<int>& a, int n, int m, int start) {
    // 递归终止条件：所有人均已出圈
    if (n == 0) return;

    // 1. 计算本轮出圈人的下标（注意取模）
    int target = (start + m - 1) % n;

    // 2. 输出出圈人的实际编号（以空格隔开）
    std::cout << a[target] << " ";

    // 3. 将出圈人移出数组，其后方所有元素自动左移一格
    a.erase(a.begin() + target);

    // 4. 进入下一轮递归：
    //    剩余人数减 1；左移后，下一轮起始报数者的下标恰好为 target
    josephus(a, n - 1, m, target);
}

int main() {
    // 优化 I/O 读写效率
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    if (!(std::cin >> n >> m)) return 0;

    // 初始化圈内人员编号 1 ~ n
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        a[i] = i + 1;
    }

    // 从下标 0（即编号 1 的人）开始第一轮报数
    josephus(a, n, m, 0);
    std::cout << "\n";

    return 0;
}

---

5. 复杂度分析

• 时间复杂度：
  • 递归深度为 $n$ 层；
  • 每一层调用 a.erase() 需要搬移 $O(k)$ 个元素，其中 $k$ 从 $n$ 递减至 1；
  • 总时间为 $\sum_{k=1}^n O(k) = O(n^2)$。
  • 本题中 $n \le 100$，最大运算次数在 $10^4$ 量级，耗时在数毫秒以内，轻松 AC。
• 空间复杂度：
  • 动态数组占用 $O(n)$ 的空间；
  • 递归调用栈深度为 $n$，栈空间占用 $O(n)$；
  • 总体额外空间复杂度为 $O(n)$。

---

6. 知识拓展：只求“最终幸存者”的 $O(n)$ 递推解法

本题要求按序输出所有人的出圈序列，因此 $O(n^2)$ 的模拟不可避免（或借助平衡树/线段树优化到 $O(n \log n)$）。

但在经典的约瑟夫环面试题中，通常只关心最后活下来的是哪一个人。针对该场景，存在一种空间 $O(1)$、时间 $O(n)$ 的反向数学递推解法：

设 $f(i)$ 为 $i$ 个人报数时最终胜出者的下标（0-indexed）：

$$f(i) = (f(i - 1) + m) \bmod i \quad (f(1) = 0)$$

核心直觉：
当规模为 $i$ 时，第一个被淘汰的人下标是 $(m - 1) \bmod i$。淘汰后，胜出者在新一轮的相对位置等于其在规模 $i-1$ 时的下标，只需加上位移量 $m$ 并对当前人数 $i$ 取模，即可倒推出其在规模 $i$ 下的原始下标。该方法无需任何数组模拟，一个单重循环即可求解。