🧩 约瑟夫出局问题题解（Josephus Problem）
问题简介
有 ( n ) 个人围成一圈，从第一个开始报数，每报到第 ( k ) 个时，该人出局。 然后从下一个人重新从 1 开始报数，循环，直到所有人都出局。
要求：输出出局顺序 或者幸存者。
- 最开始，我是在学习数据结构刷题时遇到士兵队列问题。它是约瑟夫问题的一个变式，此处不展开。
- 之后在学校的 PTA 历史题目集中的18届现场赛A题再次遇到本题。最初用暴力法勉强通过，但在梳理过程中不断冒出新疑问、找到新思路，也发现网上资料零散，于是整理这篇题解，主要也是提升自己的理解。
- 我们在做题前需要明确：
- 真实编号从 1 开始；本文若不特别说明，下标从 0 开始。
- 报数越过末尾需要“绕圈”，使用取模实现；注意这里的模是对“当前剩余人数”取模。
- 文中将明确“下标/编号”，避免混淆。
暴力模拟输出出局顺序
🧠 思路
最直观的思路： 我们每次从 people 数组中删除第 k 个出局的人。 删除后，下一个人从 1 重新报数。
💻 实现
vector<int> baoli(int n, int k) {
vector<int> people, result;
for (int i = 1; i <= n; i++) people.push_back(i);//初始化真实编号
int pos = 0, cnt = 0;
while (!people.empty()) {
cnt++;
if (cnt == k) {
result.push_back(people[pos]);//传值
people.erase(people.begin() + pos);//动态变化，值删了，大小也变小，但是每次erase复杂度都是O（n）。
cnt = 0;
} else pos++;
if (pos >= (int)people.size()) pos = 0;
}
return result;
}📊 示例：n = 5, k = 3（与上文定义一致）
| 轮次 | 当前队列 | 报数顺序 | 出局者 | 剩余队列 |
|---|---|---|---|---|
| 1 | [1,2,3,4,5] | 1,2,3 | 3 | [1,2,4,5] |
| 2 | [1,2,4,5] | 4,5,1 | 1 | [2,4,5] |
| 3 | [2,4,5] | 2,4,5 | 5 | [2,4] |
| 4 | [2,4] | 2,4,2 | 2 | [4] |
| 5 | [4] | 4 | 4 | [] |
🔹 出局顺序：3 → 1 → 5 → 2 → 4 🔹 最后幸存：4号
应用数学公式
最开始我把自己的暴力法发给ds让他纠错，提出建议，他直接把这个数学公式应用了进来
vector<int> baoli_math(int n, int k) {
vector<int> people, result;
int pos = 0;
while (!people.empty()) {
pos = (pos + k - 1) % people.size(); // 这里，计算要删除的位置
result.push_back(people[pos]); // 将出局的人加入结果
people.erase(people.begin() + pos); // 从列表中删除出局的人
}
return result;
}- 因此我遇到的第一个问题是：这个公式怎么来的？如何直观理解？
查阅资料并结合实践，我的理解是：
- 每一轮固定报 (1) 到 (k)，转成下标即 (0) 到 (k-1)，这就是公式中的 (k-1)。
- 当到达末尾，需要从开头继续，使用取模实现。这里的模是当前的
people.size()（当前剩余人数）。
公式其他应用场景
翻资料时发现，最经典的应用是只求最后的幸存者。
⚙️ 核心思路
数学法的本质是：
我们不关心过程，只关心最后幸存者的位置。
它从“反向”角度考虑：
- 已知 (n-1) 个人时最后幸存者的下标；
- 当人数变成 (n) 时，这个位置整体右移 (k) 位；
- 若越界就取模回到前面。
于是得到递推：
f(1, k) = 0
f(n, k) = (f(n-1, k) + k) % n其中 f(n, k) 是最后幸存者的下标（0 开始）。
🧾 举例：n = 5, k = 3
我们一步步列出：
| n | 推导公式 | 计算结果/被踢 | 解释 |
|---|---|---|---|
| 1 | f(1,3)=0 | 0 | 只有一个人，当然是选中下标0号 |
| 2 | (0+3)%2 | 1 | 第3个是下标1号（两人中下标[0,1]） |
| 3 | (1+3)%3 | 1 | 上一轮幸存的事下标1号，n为3人即下标边界为2，这轮报数2，0，1，选中1 |
| 4 | (1+3)%4 | 0 | 4人下标边界为3，在上轮下标1后开始，2，3，0，选中0 |
| 5 | (0+3)%5 | 3 | 边界4，上轮0后开始，1，2，3，最后幸存者/选中者是3号（下标从0起） |
因此最终幸存者编号 = 3 + 1 = 4号（下标加一为编号）。
推荐使用场景
| 目标 | 推荐方法 | 说明 |
|---|---|---|
| 输出出局顺序 | ✅ 暴力模拟 / 动态删除 | 直观易懂，便于验证 |
| 只求最后幸存者 | ✅ 数学递推法 | 高效，时间复杂度 O(n) |
| 验证理论或公式 | ✅ 数学法 | 推导简洁、递归关系清晰 |
拓展1：只输出最后一个人（最优写法）
int josephus_last(int n, int k) {
int res = 0;
for (int i = 2; i <= n; i++)
res = (res + k) % i;
return res + 1; // 从1开始编号
}- 于是我遇到了第二个疑惑
- 为什么是2开头的？答案是f（1，k）= 0很显然；
虽然答案很简单，但是多想一想多写一写印象会更深点。 例如：
(5,3)→ 输出4（即第4号幸存）。
拓展2：程序设计18届现场赛K
- 事实上，开篇约瑟夫问题还有困难版本。
- 困难版本的主要要求如下：
- n 的最大值：1.5 × 10⁶。
- 输出结果：Σ(轮数 × 出局编号) mod 2⁶⁴。
- 使用 O(n²) 的暴力解法，会导致超时。
目前还不会，以下技能点均还未解锁，做不来。
要求能力
- 🚩 算法基础
- 时间复杂度分析
- 二分思想
- 前缀和思想
- 🚩 树状数组核心
- 单点修改 + 区间查询（log n）
- 🚩 二分查找
- 在树状数组上找第 k 个 1（顺序统计）
- 🚩 环形模拟逻辑
- 约瑟夫环中位置转移与取模处理
- 🚩 大数据优化
- long long / ull 防溢出
- 快速IO
- O(n log n) 控制
为什么数学方法更适合困难版本？
| 对比项 | 暴力法 | 数学方法 |
|---|---|---|
| 时间复杂度 | O(n²) | O(n) |
| n=1.5×10⁶ 时 | 约 2.25×10¹² 操作 | 1.5×10⁶ 操作 |
| 实际运行 | 严重超时 | 瞬间完成 |
环状字符串的最小字典序（Circular Sequence, ACM/ICPC Seoul 2004, UVa1584）
注：本人写题解一方面为了加深印象，另一方面为了锻炼自己的代码和逻辑能力，还有就是想变强。
问题简介
这题要求我们给定一个环状DNA串（只包含A、C、G、T这四个字符），通过从不同位置开始读取，找出这个环状串的最小字典序表示法。说白了，环状串就是从不同位置切开然后拼起来得到的各种字符串，我们要在这些里面找到字典序最小的那个。
比如"CGAGTCAGCT"这个串，可以表示成"GAGTCAGCTC"、"AGTCAGCTCG"等等（想像成一个环）。在这些表示法里，字典序最小的就是我们要找的"最小表示"。
在做这题之前，有几个概念得先搞清楚（我当初也是查了才知道，弄明白后理解起来就简单多了）：
字典序：就是按字母顺序比较，举个例子就懂了：
比如： "ABC" < "ABD"（因为第三个字符'C'比'D'小） "AB" < "ABC"（因为"AB"是"ABC"的前缀） "AC" > "ABD"（因为第二个字符'C'比'B'大）
环状结构：既然是环状的，那走到最后肯定要回到开头，这时候用%运算符就特别方便。
思路
- 一开始我们不知道从哪里开始比较最小，那就干脆全都试一遍。遇到更小的就把它设为新的起始位置。
- 但要是把所有可能的字符串都生成出来再比较，效率太低了，长度大的话肯定会超时。
- 所以我们就从两个位置开始，逐个字符比较。
- 注意是环状的，用模运算处理边界问题。
基于这个思路，我设计了比较函数的伪代码：
比较位置p和q：
对于 i 从 0 到 n-1:
字符A = s[(p+i)%n]
字符B = s[(q+i)%n]
如果 A != B:
返回 A < B //如果a小于b就返回真（1），否则返回假（0）
返回 false（相等）说实话，我第一反应是想用strcmp来比较字符串，但因为环状结构的特殊性，用strcmp（比较线性）反而更麻烦。
试着写一下比较函数：
int less(const char*s, int p, int q){
int n = strlen(s);
for(int i = 0; i < n ;i++){
if(s[(p+i)%n]!=s[(q+i)%n]) return s[(p+i)%n] < s[(q+i)%n];
}
return 0;//完全相等
}- 再来考虑主函数。框架其实不难，但得想全面点，不然后面找bug更花时间，前期慢就是快嘛。
- 所有位置都覆盖到了吗？0~n-1
- 边界问题处理了吗？
- 特殊情况考虑了吗？比如所有字符相同、单个字符？
- 输出格式对不对？
主函数的伪代码：
初始化 ans = 0（假设位置0最小）
对于 i 从 1 到 n-1:
如果 位置i 比 位置ans 小:
ans = i
从位置ans输出整个字符串- 现在写完整代码，然后测试一下：
#include<stdio.h>
#include<string.h>
#define maxn 105
int less(const char*s, int p, int q){
int n = strlen(s);
for(int i = 0; i < n ;i++){
if(s[(p+i)%n]!=s[(q+i)%n]) return s[(p+i)%n] < s[(q+i)%n];
}
return 0;//完全相等
}
int main() {
int T;
char s[maxn];
scanf("%d", &T);
while(T--) {
scanf("%s", s);
int n = strlen(s);
// 初始化最小位置
int ans = 0;
// 遍历比较所有位置
for(int i = 1; i < n; i++) {
if(less(s, i, ans)) {
ans = i; // 找到更小的就更新
}
}
// 输出结果
for(int i = 0; i < n; i++) {
putchar(s[(ans+i)%n]);
}
putchar('\n');
}
return 0;
}- 算一下复杂度：字符串长度N，测试用例T
- strlen 是O(N)
- while循环执行T次
- for循环 + less函数调用是O(N²)
- 最后的输出循环是O(N)
所以总复杂度是O(T × N²)，对于题目给的数据范围完全够用了。
更高效的Booth算法
前面我们介绍了O(n²)的暴力解法，当长度很大时，显然会超时，通过搜索资料，我们来看看更高级的O(n)解法——Booth算法。一起学习。
Booth算法完整代码
int booth(const char* s) {
int n = (int)strlen(s);
int i = 0, j = 1, k = 0;
while (i < n && j < n && k < n) {
char a = s[(i + k) % n];
char b = s[(j + k) % n];
if (a == b) {
k++;
continue;
}
if (a > b) {
i = i + k + 1;
if (i <= j) i = j + 1;
}
else {
j = j + k + 1;
if (j <= i) j = i + 1;
}
k = 0;
}
int ans = i < j ? i : j;
return ans;
}Booth算法怎么用
while(T--) {
scanf("%s", s);
int ans = booth(s); // 直接用Booth算法找最小位置
// 输出结果（跟之前一样）
}双指针竞争
i和j像两个选手在比赛- 它们从相邻位置开始比较（i=0, j=1）
k记录当前已经匹配的字符数
智能跳跃 - 精髓！
当发现某个位置不可能是最小值时，直接跳到下一个可能的位置，跳过中间那些肯定更大的位置。
举个例子： 假设字符串是"abcabc"，比较i=0和j=1：
- 前3个字符都相同（k=3）
- 第4个字符：i位置是'a'，j位置是'b'
- 因为'a' < 'b'，所以j位置肯定不是最小，直接跳到j=4
3. 为什么能跳那么远？
因为如果前k个字符都相同，第k+1个字符不同，那么：
- 输的那一方（字符较大的）及其后面k个位置都不可能是最小表示
- 所以直接跳到
当前位置 + k + 1
复杂度对比
| 算法 | 时间复杂度 | 适用场景 |
|---|---|---|
| 暴力法 | O(n²) | n ≤ 1000，代码简单 |
| Booth算法 | O(n) | n > 1000，需要高效 |
实际测试
两种方法都试过：
- 当n=100时，两种方法速度差不多
- 当n=10000时，暴力法要等好几秒，Booth算法瞬间出结果
- 当n=100000时，暴力法直接超时，Booth算法依然很快
使用建议
- 比赛时：如果n≤1000，用暴力法更稳妥（不容易写错）
- 大数据时：n>10000，一定要用Booth算法
- 学习时：两种都要会，理解思想更重要