C语言学习笔记20260625-约瑟夫环（2种方法）

一、学习目标

通过经典的“约瑟夫环”问题，掌握计算机解决循环淘汰类问题的两种核心范式。深入理解“物理模拟法”中动态数组的缩圈逻辑，并探究“数学递推法”如何将复杂的模拟过程降维成一行简洁的公式，体会算法从“直观”到“极致优化”的思维跃迁。

二、问题拆解与核心逻辑

本题要求 n个人（编号 0 - n-1）围成一圈，从编号 k开始报数，每报到m的人出局，直到剩下最后一人。核心约束条件为：

1. 环形结构：队伍首尾相连，报数到队尾后需自动回到队首。
2. 动态缩圈：有人出局后，队伍长度减 1，且下一轮报数从出局者的下一个人无缝衔接。
3. 起始偏移：报数并非总是从编号 0 开始，而是从指定的编号 k开始。

三、方案一：模拟队列法（物理缩圈）

3.1 核心思路

使用一个连续数组 arr 来物理存储当前还在圈内的人。当有人出局时，直接将数组中该位置之后的所有元素向前移动一位，覆盖掉出局者。这种“缩圈”操作保证了数组始终是紧凑的，下标 0 - len-1 永远对应当前存活的len个人。

3.2 代码解析与难点突破

int len = n;
int cur = k; // 当前起始报数位置下标
while (len > 1)
{
    // 核心公式：计算出局者在当前数组中的下标
    cur = (cur + m - 1) % len;
    // 物理删除：后面元素前移覆盖
    for (int i = cur; i < len - 1; i++)
        arr[i] = arr[i + 1];
    len--; // 队伍长度减 1
}

3.3 核心技巧与优缺点

• 动态下标计算：cur = (cur + m - 1) % len 是此算法的精华。因为当前从 cur 开始报“1”，所以报到“m”的人相对于 cur 的偏移量是 m-1。取模 % len 完美解决了环形越界问题。
• 无缝衔接：由于数组前移，出局者后面的那个人会自动填补到 cur 这个下标位置。因此，下一轮循环开始时，cur 不需要额外调整，直接作为新的起点即可。
• 优缺点：逻辑极其直观，但由于每次删除都需要移动元素，时间复杂度为 O(n^2)，仅适用于n较小（如 n<1000）的场景。

四、方案二：数学公式法（极致优化）

4.1 核心思想：逆向递推

不模拟淘汰过程，而是通过数学归纳法寻找规律。假设我们知道n-1个人时幸存者的下标f(n-1)，那么n个人时幸存者的下标f(n)可以通过相对位移推导出来。

4.2 递推公式推导

• 基础公式：设f(i)为i个人时最后存活的下标（默认从 0 开始报数）。
  • f(1) = 0 （只剩 1 人时，幸存者下标必为 0）
  • f(i) = (f(i-1) + m) % i （i>1) 时，幸存者位置等于上一轮结果向后偏移 m位，并对当前人数取模）
• **处理起始偏移 k：标准公式是基于从编号 0 开始报数的。本题从编号 k开始，相当于整个环旋转了k位。因此，最终结果需要加上偏移量 $k$ 并对总人数 $n$ 取模：
  • ans = (f(n) + k) % n

4.3 代码实现

int res = 0;
// 从 2 个人开始，逐步递推到 n 个人
for (int i = 2; i <= n; i++)
    res = (res + m) % i;
// 修正起始位置 k 的偏移
res = (res + k) % n;
printf("%d", res);

4.4 优缺点

• 优点：时间复杂度仅为 O(n)，空间复杂度 O(1)。即使 n达到 10^8 甚至更大，也能瞬间算出结果。
• 缺点：需要较强的数学推导能力，代码虽然简短，但如果不理解背后的递推逻辑，很难直接写出。

五、总结

总结：
方案一展示了计算机“暴力模拟”的强大能力，通过数组的动态操作将复杂的环形淘汰具象化，是理解问题本质的基石。方案二则体现了数学在计算机科学中的降维打击能力，通过寻找规律将n轮复杂的淘汰过程浓缩为一个简单的迭代公式。在实际工程与算法竞赛中，我们应当根据数据规模灵活选择：小规模数据用模拟法确保正确与直观，大规模数据则必须依赖数学公式实现性能飞跃。