引入约瑟夫环

约瑟夫环是个很有意思的问题，本质上是个模拟题：

有n个小朋友围成一圈玩点名游戏，他们首尾相接，也就是从n号小朋友往下一个，又回到1号小朋友。
小朋友们从1号开始报数，到第m号小朋友时，这位小朋友出局。从下一位小朋友处重新从1开始报数。
这样玩下去，直到最后只剩一位小朋友，他就是胜利者。
请你找出这位小朋友。

但是模拟下去，比如我们用一个循环链表或者循环数组（用取模首尾相连）来做也是 OK 的。但这样的时间复杂度是无法接受的，但我们是有办法通过归纳总结用数学算法来化简复杂度：
这里介绍一种线性解法：

数学理解

算法的本质是 逐步预测人数增加时幸存者的变化。
我们从正推来看：
当有 5 个人时，每数到 3 个就出局这个人:

• 最初： 0 1 2 3 4
  第三个数为 2，把它出局。
• 第二轮: 3 4 0 1
  第三个数为 0 出局
• 第三轮：1 3 4
  第三个数为 4 出局
• 第四轮：1 3
  第三个数为 1 出局，只剩下此时只剩下 3 。所以 3 是最终答案。

引入递归式：
$J_{n, k}=(J_{n-1, k} + k) \mod n$

这里取模主要是为了达到数组回绕的效果，当超过长度时把它拉回区间内。
可以发现最后一个数即是幸存者，我们的逆向思维可以考虑从后往前推寻找幸存者此时所在的坐标，直到推到最开始的坐标。

代码实现

1
2
3
4
5
6
7
8
9

int josephus(int n, int k)
{
    int res = 0;
    for (int i = 1; i <= n; ++i)
    {
        res = (res + k) % i;
    }
    return res;
}

到这里还是很难理解……
主要是这行逻辑：

1

res = (res + k) % i;

因为在循环开始是最后一次，也就是只剩下幸存者的时候，此时坐标为 0，而且此时 i=1 取模肯定为 0。
而后往前一直推有如下：

1
2
3
4
5

(0+3)%1=0
(0+3)%2=0
(0+3)%3=0
(1+3)%4=0
(0+3)%5=3

结果一致！
算法 res 表示在这些人里，幸存者是当前的编号。显然，每次轮询都会重新排序。
该算法不是逆向还原被剔除的人，这是我花了好久才理解到的地方，其取模操作确保了编号在有效范围内循环。

+k 是为了找回在这次点名前幸存者的编号。它是回答在小圈子中的幸存者在大圈子中坐在哪里。

参考资料

1. OI Wiki 约瑟夫问题
2. 约瑟夫环问题（线性解法和对数解法）
3. DeepSeek(问了好几个大回合才理解😭)