数组的约瑟夫环：从模拟到数学的思维跃迁

约瑟夫环问题，我最早是在大学数据结构课上遇到的。当时觉得这题挺有意思——一群人围成一圈报数，每数到第k个人就淘汰，最后剩下谁？用数组模拟起来很直观，但后来我在一个嵌入式项目中真正用到类似算法时才发现，纯模拟在大数据量下根本跑不动。嗯，今天我们就来聊聊这个问题，从数组模拟讲到数学解法，看看怎么从“暴力模拟”进化到“数学推导”。

问题描述：到底什么是约瑟夫环？

简单说，就是n个人编号0到n-1，围成一圈。从0开始报数，每报到k-1的人出局，然后从下一个人重新从0开始报。重复这个过程，直到只剩一个人。问最后剩下的是谁？

举个例子：n=5，k=2。也就是5个人，每数到2的人淘汰。

• 初始：0, 1, 2, 3, 4
• 第一轮：数到1的人（编号1）出局，剩下0, 2, 3, 4
• 第二轮：从2开始数，数到3的人（编号3）出局，剩下0, 2, 4
• 第三轮：从4开始数，数到0的人（编号0）出局，剩下2, 4
• 第四轮：从2开始数，数到4的人（编号4）出局，最后剩下2

所以答案是2。你想想看，如果用手算，n=5还好，要是n=10000呢？

数组模拟法：最直观的思路

我个人习惯先用数组模拟法理解问题。思路很简单：用一个数组标记每个人是否还在圈里。然后循环遍历，遇到出局的人就跳过，直到只剩一个人。

#include <stdio.h>

int josephus_array(int n, int k) {
    int alive[n];  // 1表示还在，0表示出局
    for (int i = 0; i < n; i++) {
        alive[i] = 1;
    }
    
    int count = n;      // 剩余人数
    int index = 0;      // 当前报数位置
    int step = 0;       // 报数计数器
    
    while (count > 1) {
        if (alive[index] == 1) {
            step++;
            if (step == k) {
                alive[index] = 0;  // 淘汰
                count--;
                step = 0;
            }
        }
        index = (index + 1) % n;  // 环形移动
    }
    
    // 找到最后活着的人
    for (int i = 0; i < n; i++) {
        if (alive[i] == 1) return i;
    }
    return -1;
}

int main() {
    int n = 5, k = 2;
    printf("最后剩下: %d\n", josephus_array(n, k));
    return 0;
}

这段代码跑起来没问题，但效率如何？时间复杂度是O(n*k)，空间复杂度O(n)。我在项目中遇到过类似场景，n是10万级别，k是3位数，结果程序跑了几秒才出结果。对于实时系统来说，这完全不可接受。

数学解法：从递推公式到O(n)解法

为什么会想到数学解法？因为约瑟夫环问题本质上是一个递推关系。我们定义f(n, k)为n个人、步长为k时最后幸存者的编号。那么f(1, k) = 0，这是显然的——只有一个人，他就是幸存者。

关键是递推公式：f(n, k) = (f(n-1, k) + k) % n

这个公式怎么来的？我解释一下：

• 第一轮淘汰了第k-1号人（从0开始编号）
• 剩下n-1个人，重新编号。原来的第k号变成了新的0号，第k+1号变成了新的1号……
• 如果我们知道了n-1个人时的幸存者编号f(n-1, k)，那么它在原编号中就是(f(n-1, k) + k) % n

说白了，这就是一个“映射还原”的过程。你想想看，是不是很巧妙？

#include <stdio.h>

int josephus_math(int n, int k) {
    int survivor = 0;  // f(1, k) = 0
    for (int i = 2; i <= n; i++) {
        survivor = (survivor + k) % i;
    }
    return survivor;
}

int main() {
    int n = 5, k = 2;
    printf("最后剩下: %d\n", josephus_math(n, k));
    return 0;
}

这段代码只有几行，时间复杂度O(n)，空间复杂度O(1)。我在项目中用这个解法处理过n=1000万的数据，几乎是瞬间出结果。差距就是这么大。

两种方法的对比与选择

我个人建议：

• 学习阶段：先用数组模拟法理解问题逻辑，再推导数学公式。这样能加深理解。
• 实际项目：直接用数学解法。除非你需要记录每一步淘汰的人是谁，否则别用模拟。
• 面试场景：先讲数组模拟，再引出数学解法。面试官会欣赏你从暴力到优化的思维过程。

知识体系图：约瑟夫环的两种解法

总结：从模拟到数学的思维跃迁

约瑟夫环问题，其实是一个很好的思维训练案例。数组模拟法让我们理解问题本身，数学解法则展示了如何用递推思想优化算法。我个人觉得，这种“先暴力后优化”的学习路径，比直接给最优解更有价值。

你想想看，如果面试官问你约瑟夫环，你直接甩出数学公式，他可能会觉得你背题。但如果你先讲数组模拟，再分析性能瓶颈，最后引出递推公式，这就能体现出你的思考深度。嗯，我在面试中就是这么做的，效果不错。

最后提醒一句：数学解法虽然快，但如果你需要记录每一步淘汰的人是谁，那还是得用数组模拟。工具没有好坏，关键看场景。

公众号:蓝海资料掘金营，微信deep3321