约瑟夫环
这个问题来源于犹太人约瑟夫经历过的故事，在罗马人占领乔塔帕特后，约瑟夫和他的朋友与39 个犹太人躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人时，该人就必须自杀，然后再由下一个人重新报数，直到所有人都自杀身亡为止。
然而约瑟夫和他的朋友并不想遵从这个规则，于是，他们想出新的思路：从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。
将问题抽象一下：现在有 $n$ 个人围成一圈按顺序编号为 $1\sim n$。从 $1$ 号开始按照 $1、2、3、、、k$ 的顺序报数，报 $k$ 者退出，然后从下一个人开始继续从 $1$ 开始报数，知道只剩下一个人，求剩下这个人的编号。
例如：
如：N=6，k=5
1 2 3 4 $\underline 5$ 6
1 2 3 $\underline 4$ 6
1 2 3 $\underline6$
1 $\underline2$ 3
1 $\underline3$
1
最终剩下编号 $1$。
朴素解法
模拟
模拟整个选人的流程，每次去除一个人，直至剩下最后一个。
可以使用环形链表或者数组。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int flag[N] ;
int main()
{
int n, k;
cin >> n >> k;
int cnt = n;
int id = 0;
while (cnt != 1) {
int t = 0;
do{
id = id % n + 1;
if (!flag[id]) {
t ++;
}
}
while (t < k);
flag[id] = 1;
cnt --;
}
for (int i = 1; i <= n; i ++)
if (!flag[i])
cout << i;
return 0;
}
时间复杂度：$O(n\times k)$。
数学优化
当 $n$ 个人围成一圈并以 $k$ 为步长第一次报数时，第 $k$ 个人出列，此时就又组成了一个新的人数为 $n-1$ 的约瑟夫环。要求 $n$ 个人的约瑟夫环问题的解，就依赖于求 $n-1$ 个人的约瑟夫问题的解，要求 $n-1$ 个人的约瑟夫问题的解，则依赖于求 $n-2$ 个人的约瑟夫换问题的解，依次类推，直至求 $1$ 个人的时候，该问题的解。
递推公式：$f(N,M)=f((N-1,M)+M)\%N$。
其中，$f(N,M)$ 表示 $N$ 个人报数，将报到 $M$ 的人杀掉，最终胜利者的编号。
推导过程：
举例：11个人参与游戏，每报到3的人被杀掉
第一轮：从No.1开始报数，No.3被杀
第二轮：No.4从1开始报数，这时可以认为队伍的头是No.4，No.6被杀
……
第九轮：No.2从1开始报数，成为队伍的头，No.8被杀
第十轮：No.2从1开始报数，……No.2被杀
胜利者为No.7
关键
假设①：当游戏中剩余11人时，我们知道最终胜利者为No.7（对应数组下标为 6 ）。那么下一轮剩余10人时，最终胜利者No.7的下标变成 3。因为删掉No.3后，后面的人都往前移动了3位（每杀掉一个人，下一个人成为头，相当于把数组向前移动 k 位，6 - 3 = 3，所以最终胜利者下标变为 3）；
假设②：当游戏中剩余10人时，我们知道最终胜利者的下标为 3。那么下一轮剩余11人时，最终胜利者的编号是几？该问题可以看作假设①的逆过程，因此：$f(11,3)=f(10,3)+3 = 6$
为防止数组越界，对当前人数取模：$f(11,3)=(f(10,3)+3)\%11=6$。数组下标为 6，对应的编号为 No.7。
假设③：游戏中剩余 $N$ 人，报到 $k$ 者被杀，数组移动情况为：每杀一个人，下一个人成为头，相当于把数组向前移动 $k$ 位。若已知剩余$N-1$人时最终胜利者下标为 $f(N-1,k)$，则 $N$ 个人时，就是往后移动 $k$ 位。因此推导出递推公式：$f(N,k)=(f(N-1,k)+k)\%N$。
核心：最终胜利者的下标位置的变化。每去除一个人，其实就是把这个数组向前移动了 $k$ 位。然后逆过来，就可以得到这个递推式。因为求的是数组标，最终的编号还要加 1。
代码
// 递归
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int solve(int n, int k) {
if (n == 1)
return n;
return (solve(n - 1, k) + k - 1) % n + 1;
}
int main() {
int n, k;
cin >> n >> k;
cout << solve(n, k);
return 0;
}
复杂度
- 时间复杂度：$O(n)$。
- 空间复杂度：$O(n)$，递归栈的空间。
// 迭代
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int solve(int n, int k) {
if (k == 1)
return n;
int p = 0;
for (int i = 2; i <= n; i ++)
p = (p + k) % i;
return p + 1;
}
int main() {
int n, k;
cin >> n >> k;
cout << solve(n, k);
return 0;
}
复杂度
- 时间复杂度：$O(n)$。
- 空间复杂度：$O(1)$。
