Lesson 10: 约瑟夫环 CNB
练习任务
本课包含两个递进练习：
练习 1（init_ring & print_ring）：初始化一个模拟循环链表的 next[] 数组——next[i] = (i + 1) % n，使 n-1 号位的下一个指向 0 号位，形成闭环。读入 n 后打印 next[0] 到 next[n-1]，每个数字后跟一个空格。
期望输出（n=5）：
1 2 3 4 0练习 2（Josephus）：在 next[] 循环链表上完成约瑟夫环淘汰——10 个人围成圈，每数到第 3 个人出局（ALL=10, OUT=3）。跟踪计数 counter，记录前驱 prev，出局时通过 next[prev] = next[i] 将出局者从链中移除。
期望输出：
3 is out
6 is out
9 is out
2 is out
7 is out
1 is out
8 is out
5 is out
10 is out
4 is out提示：约瑟夫环的核心是「环形遍历 + 计数淘汰」。用数组
next[i]记录第i个人的下一个人是谁——这等价于链表中的next指针，但无需struct和malloc。出局时需要知道「前一个人」是谁，这样才能修改链表跳过出局者。取模%是实现循环索引的关键工具。
核心知识点
- 约瑟夫环问题 — n 人围圈，每数到第 m 个出局，求最后一个幸存者；源自公元 1 世纪真实历史事件
- 数学递推公式 —
f(1)=0; f(n)=(f(n-1)+m)%n，O(n) 时间直接计算幸存者位置 - 数组模拟循环链表 —
next[i] = (i + 1) % n用数组下标实现指针链，无需 struct 和 malloc - 取模实现环形索引 —
pos = (pos + 1) % n保证索引在 0~n-1 之间循环，是环形数据结构的数学基础 - 标志删除法 — 将出局者值置 0，后续遍历时跳过值为 0 的位置；简单但 O(n²) 复杂度
- 链表跳转法 —
next[prev] = next[i]从链中移除节点，O(1) 删除，整体 O(n*m) 复杂度 - 全局数组 — 函数间共享数据，无需传参，适合简单程序的数据结构
- 局部数组 — 函数内部声明，作用域限制，适合模块化设计和大程序
#define宏常量 — 编译前文本替换，一次定义多处使用；数组长度必须用宏（C89/C90）const限定符 — 编译期类型检查，有符号信息，但不适用于 C89 数组长度声明- 条件编译
#if/#else— 同一套源码中保留两种实现的编译器级别切换，零运行时开销 - 计数器状态机 —
step/counter跟踪当前数到第几步、何时触发淘汰，是有限状态机的最简实例 - 数据驱动编程 — 数据结构选择决定算法效率（Rob Pike 哲学）
- XOR 交换 —
a ^= b; b ^= a; a ^= b;实现无临时变量的原地交换 - struct 方案 vs 数组方案 — 用结构体封装链表节点与用下标数组模拟的权衡
- 循环缓冲区 — 固定大小的环形队列，广泛应用于操作系统、网络协议、音视频处理
代码框架
练习 1：初始化循环链表
#include <stdio.h>
#define MAX 1000
int next[MAX];
int n;
void init_ring(void)
{
int i;
// next[i] = (i + 1) % n —— 最后一个人的下一人是第 0 个
for (i = 0; i < n; i++)
/* 填写 next[i] 的值 */;
}
void print_ring(void)
{
int i;
// 打印 next[0] 到 next[n-1]，每个后面跟一个空格
}
int main(void)
{
scanf("%d", &n);
init_ring();
print_ring();
return 0;
}练习 2：约瑟夫环淘汰
#include <stdio.h>
#define ALL 10
#define OUT 3
int next[ALL];
void init_ring(void)
{
int i;
for (i = 0; i < ALL; i++)
next[i] = (i + 1) % ALL;
}
int main(void)
{
int left = ALL; // 剩余人数
int counter = 0; // 数到第几个
int i = 0; // 当前指向谁
int prev = ALL - 1; // i 的前一个人是谁（初始化为最后一人）
init_ring();
// while (left > 0)
// {
// counter++;
// if (counter == OUT)
// {
// printf("%d is out\n", i + 1);
// // 从链表中删除 i —— 让 prev 跳过 i
// next[prev] = /* 填空 */;
// left--;
// counter = 0;
// }
// prev = i;
// i = next[i]; // 前进到下一人
// }
return 0;
}填充框架的关键思考：prev 的初始值为什么是 ALL - 1（最后一个人）？出局时为什么是 next[prev] = next[i] 而不是 next[prev] = i + 1？
TIP
先不要往下翻看参考解答。先在纸上画一个 5 人环，手动模拟一遍淘汰过程——理解 prev 的角色至关重要。
深度讲解
1. 约瑟夫环：一个流传千年的数学问题
1.1 历史起源
公元 1 世纪，犹太历史学家弗拉维乌斯·约瑟夫斯（Flavius Josephus）参与犹太反叛罗马的战争。战败后，他和 40 名战友被罗马军队包围在 Yodfat 的洞穴中。他们决定宁死不降，约定围成圈，从第一个人开始每数到第三个人就必须被同伴杀死，直到剩下最后一人。
约瑟夫斯不想死——他和另一个朋友通过快速心算站到了安全位置：第 16 号和第 31 号位置。最终两人幸存，向罗马军队投降。约瑟夫斯后来成为罗马公民，写出了《犹太战记》等重要历史著作。
这正是约瑟夫环问题的文学起源：已知 n = 41 人，m = 3，求最终幸存位置。
1.2 问题的数学化表述
给定 n 个人围成一圈（编号 0, 1, 2, ..., n-1），从 0 号位置开始计数，每数到第 m 个人（含当前正在数的人）令其出局，然后从出局者的下一位重新开始数 1。求：
- 出局顺序：每个人按什么顺序离开
- 幸存者位置：最后剩下的人位于哪个编号
n=5, m=3 的淘汰过程:
初始: [1] [2] [3] [4] [5]
索引: ↑0 ↑1 ↑2 ↑3 ↑4
数到 3: [1] [2] --- [4] [5] → 编号 3（索引 2）出局
↑3 ↑4 ↑0 ↑1 （从出局者下一位重新开始数）
数到 3: [1] --- --- [4] [5] → 编号 1（索引 0）出局
↑2 ↑3
数到 3: --- --- --- [4] [5] → 编号 5（索引 4）出局
↑0 ↑1 ↑2
数到 3: --- --- --- [4] --- → 编号 2（索引 1）出局
↑3 ↑0 ↑1
最后: --- --- --- [4] --- → 编号 4（索引 3）幸存1.3 为什么选这个题目
约瑟夫环不是一道简单的编程练习——它是数据结构、算法分析和数学思维的交叉训练场：
| 层面 | 学到的能力 |
|---|---|
| 数据结构 | 用数组模拟链表（下标替代指针） |
| 算法设计 | 环形遍历、计数淘汰、状态管理 |
| 数学分析 | 递推公式推导、时间复杂度证明 |
| 编程技巧 | 取模运算符、条件编译、宏常量 |
| 工程哲学 | 数据结构优先于算法（Rob Pike） |
这个题目将贯穿你的整个编程生涯——从入门时的数组模拟，到算法课上的数学推导，再到操作系统中的轮转调度，约瑟夫环的影子无处不在。
2. 数组模拟循环链表
2.1 next[i] 的语义
在传统的链表中，每个节点有一个 next 指针指向下一个节点。在约瑟夫环中，我们用数组下标替代指针：
int next[ALL];
void init_ring(void)
{
int i;
for (i = 0; i < ALL; i++)
next[i] = (i + 1) % ALL;
}next[i] 存储的是第 i 个人的下一个人是谁——用下标编号表示。如果 n=5：
next[0] = (0+1)%5 = 1 → 0 号的下一人是 1 号
next[1] = (1+1)%5 = 2 → 1 号的下一人是 2 号
next[2] = (2+1)%5 = 3 → 2 号的下一人是 3 号
next[3] = (3+1)%5 = 4 → 3 号的下一人是 4 号
next[4] = (4+1)%5 = 0 → 4 号的下一人是 0 号 ← 闭环！(i + 1) % n 正是取模实现环形的精髓——当 i = n-1 时，(n-1+1) % n = 0，自动绕回起点。不需要任何 if 判断，一个数学运算就完成了闭环。
2.2 与 struct 链表的等价性对比
为了理解「数组模拟」的精妙之处，我们先看如果用传统的 struct 链表来实现约瑟夫环：
#include <stdio.h>
#include <stdlib.h>
struct Node {
int val;
struct Node *next;
};
// 需要 malloc 分配每个节点，需要手动链接，最后还要 free| 方面 | struct Node { int val; Node *next; } | int next[n] |
|---|---|---|
| 内存分配 | malloc 堆分配（需要 #include <stdlib.h>） | 数组栈/数据段分配（自动管理） |
| 下一个节点 | node->next（真实指针，需理解 * 和 ->） | next[i]（下标模拟指针） |
| 删除操作 | prev->next = cur->next | next[prev] = next[i] |
| 遍历方式 | p = p->next | i = next[i] |
| 指针知识需求 | 需要理解指针、内存地址、解引用 | 只需数组下标 |
| 内存回收 | 需要 free 每个节点 | 自动回收（数组在栈或数据段） |
| 节点数量 | 运行时动态确定 | 编译时确定（或 VLA） |
| 节点值 | 可以存储任意复杂数据 | 下标即标识，值隐含在索引中 |
对于入门阶段，next[i] 数组将**「指针」的语义隐藏在「下标」**背后——逻辑上完全等价，语法上更友好。但理解 next[prev] = next[i] 的本质就是链表节点删除，是为后续真正链表编程铺路的关键思维跳跃。
2.3 下标模拟指针的本质
i = next[i]; // 等价于 p = p->next;
next[prev] = next[i]; // 等价于 prev->next = cur->next;这里的下标 i 扮演了双重角色：它既是指向某个「人」的标识符（类似 p->val），又是定位 next[] 数组的索引（类似 p 本身）。这种索引即标识的设计，是「数据驱动编程」的典型体现——因为数据结构选得好（数组），算法（链表遍历）就自然浮现。
2.4 可视化：数组模拟的链表拓扑
初始化后的 next[] 数组（n=5）:
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 0 │ │ 1 │ │ 2 │ │ 3 │ │ 4 │
└─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘
│ │ │ │ │
next[0]=1 next[1]=2 next[2]=3 next[3]=4 next[4]=0
│ │ │ │ │
▼ ▼ ▼ ▼ ▼
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 1 │────▶│ 2 │────▶│ 3 │────▶│ 4 │────▶│ 0 │
└───┘ └───┘ └───┘ └───┘ └───┘
▲ │
└────────────────────────────────────────────┘
闭环3. 取模运算符实现环形索引
3.1 两种环形前进方式的对比
回顾 Lesson 04 中学到的取模运算符 <——。在约瑟夫环中，取模体现了它的「限界」功能：
// 方案 A: 取模法（一行搞定）
pos = ++pos % ALL_NUM;
// 方案 B: if 判断法（更直观但较冗长）
pos++;
if (pos == ALL_NUM)
pos = 0;两段代码在功能上等价，但反映了不同的思维方式：
- if 方式想的是「如果出界就回到 0」——边界检查思维
- 取模方式想的是「用一个数学运算让结果落在 0~n-1 之间」——数学限界思维
3.2 取模的限界本质
n=5, pos 的变化过程:
0 → 1 → 2 → 3 → 4 → 0 → 1 → 2 → ...
↑
4+1=5, 5%5=0, 绕回起点取模 % n 就像一个「自动回绕器」——无论 pos 从什么值开始递增，pos % n 永远落在 [0, n-1] 区间内。这是模算术在编程中最直观的应用。
3.3 取模在约瑟夫环中的双重用途
pos = ++pos % ALL_NUM; // 用途1: 空间上的环形——位置循环
step = step % COUNT_NUM; // 用途2: 时间上的节奏——计数循环两个 % 分别处理了：
- 空间维度的环形：人在圈中循环移动
- 时间维度的节奏：数 1, 2, 3 的周期性重复
这是取模运算符普适性的绝佳展示——同一个运算符，在空间和时间两个维度上同时发挥作用。
3.4 取模的模运算性质
取模运算符 % 在 C 语言中遵循以下性质（ISO C99 标准，Section 6.5.5）：
(a + b) % n = ((a % n) + (b % n)) % n // 加法分配律
(a * b) % n = ((a % n) * (b % n)) % n // 乘法分配律这些性质在递推公式的推导中会被用到。理解取模的代数结构，是理解约瑟夫环数学解法的前提。
4. 标志删除法与链表跳转法
约瑟夫环的核心操作是「从环形结构中删除一个元素」。我们用两种不同的数据结构实现了这一操作。
4.1 标志删除法（原始 josephus.c 方案）
标志删除法用一个 people[] 数组存储每个人的编号，出局时将对应位置标记为 0（表示「已死」），但保留在数组中：
while (left > 0)
{
if (people[pos] > 0) // 这个位置的人还活着才计数
step++;
if (step == OUT_NUM && people[pos] != 0)
{
people[pos] = 0; // 标志为「已死」
left--;
}
pos = ++pos % ALL_NUM; // 无论死活都向下推进
step = step % COUNT_NUM;
}特点：不修改数据结构，只标记 people[pos] = 0。遍历时跳过值 0 的位置。
缺点：每次都要测试这个位置是否有效（if people[pos] > 0）——随着出局者增多，无效位置越来越多，浪费的比对次数越来越多。
出局人数 无效位置比例 平均扫描次数（找到下一个有效人）
1 1/100 ≈ 1 次
50 50/100 ≈ 2 次
90 90/100 ≈ 10 次
99 99/100 ≈ 100 次 ← 最后一个要扫描 100 次！4.2 链表跳转法（next[] 方案）
链表跳转法用 next[] 数组记录「下一个有效人的位置」，出局时直接修改链接关系：
while (left > 0)
{
counter++;
if (counter == OUT)
{
printf("%d is out\n", i + 1);
next[prev] = next[i]; // prev 直接跳过 i，i 从链中消失
left--;
counter = 0;
}
else
{
prev = i; // 只有当 i 没出局时才更新 prev
}
i = next[i]; // 总是跳到一个有效的人
}特点：i = next[i] 总是跳到下一个在位的人——不存在死节点遍历，每次迭代都处理一个有效的人。
关键细节——为什么 prev 只在 else 分支更新：
当 i 出局时，prev 不能更新为 i，因为 i 已经不在链中了。prev 必须保持指向链中实际存在的节点，这样下一次出局时才能正确地执行 next[prev] = next[new_i]。这是链表删除操作中最容易出错的细节。
4.3 prev 初始值的奥秘
int prev = ALL - 1; // 初始化为最后一个人为什么 prev 初始化为 ALL - 1 而不是 0 或其他值？
因为程序从 i = 0（第一个人）开始遍历。在环形链表中，第一个人的前驱是最后一个人。如果 prev 初始化为 0，那么当第一个人（i=0）需要出局时，next[0] = next[0] 不会产生正确的删除效果——需要的是 next[prev] = next[0]，即让最后一个人跳过第一个人。
环形链表中的前驱关系:
ALL-1 ──→ 0 ──→ 1 ──→ 2 ──→ ... ──→ ALL-1
↑ │
└───────────────────────────────────────┘
0 的前驱是 ALL-1，所以 prev 初始化为 ALL-1。4.4 两种方法的完整效率对比
| 标志法 | 链表法 | |
|---|---|---|
| 每次迭代 | 可能访问无效位置 | 总是处理在位的人 |
| 删除操作 | people[pos] = 0（O(1)） | next[prev] = next[i]（O(1)） |
| 找下一个有效人 | O(n) 最坏情况（扫描） | O(1)（直接跳转） |
| 额外内存 | 无（就地标记） | 额外 next[] 数组（O(n)） |
| 总时间复杂度 | O(n²) | O(n*m) ≈ O(n)（当 m 为常数） |
| 总空间复杂度 | O(n) | O(n) |
关键差异：标志法中，找到下一个有效的人需要通过循环去扫描；链表法中，next[i] 已经记录了直接跳转的路径。这就是 Rob Pike 所说的「数据结构选择决定算法效率」——两种方法的时间复杂度差异不是算法技巧造成的，而是数据结构选择造成的。
4.5 算法执行轨迹可视化
以下是 n=5, m=3 时链表跳转法的完整执行轨迹：
初始状态:
next[] = {1, 2, 3, 4, 0}
prev = 4, i = 0, counter = 0, left = 5
Step 1: counter=1, prev=0, i=1
Step 2: counter=2, prev=1, i=2
Step 3: counter=3 → 出局!
→ 打印 "3 is out" (i=2, 编号=2+1=3)
→ next[1] = next[2] = 3 (prev=1 跳过 i=2)
→ left=4, counter=0
→ next[] = {1, 3, 3, 4, 0}
→ prev 不变 (=1), i = next[2] = 3
Step 4: counter=1, prev=3, i=4
Step 5: counter=2, prev=4, i=0
Step 6: counter=3 → 出局!
→ 打印 "1 is out" (i=0, 编号=0+1=1)
→ next[4] = next[0] = 1 (prev=4 跳过 i=0)
→ left=3, counter=0
→ next[] = {1, 3, 3, 4, 1}
→ prev 不变 (=4), i = next[0] = 1
... 以此类推，直到 left=05. 全局数组与局部数组
5.1 为什么 next[] 声明为全局
#define ALL 10
#define OUT 3
int next[ALL]; // 全局数组——所有函数都能访问
void init_ring(void) { ... } // 不需要传参
int main(void) { ... } // 不需要传参全局数组避免了在函数间频繁传递数组参数——init_ring、main 都可以直接读写 next[]。这对于小型程序来说方便，但需要理解其背后的内存模型。
5.2 C 程序的内存布局
高地址 ┌──────────────┐
│ 栈 (Stack) │ ← 局部变量、函数调用帧
│ ↓ 向下增长 │
├──────────────┤
│ ... │
├──────────────┤
│ 堆 (Heap) │ ← malloc/free 动态分配
│ ↑ 向上增长 │
├──────────────┤
│ BSS 段 (未初始化) │ ← 全局未初始化变量（自动清零）
├──────────────┤
│ 数据段 (已初始化) │ ← 全局已初始化变量、static 变量
├──────────────┤
│ 代码段 (Text) │ ← 程序指令、只读数据
低地址 └──────────────┘int next[ALL]; 作为全局变量，被分配在 BSS 段（如果未初始化）或数据段（如果初始化了）。这意味着：
- 它在程序启动时就已经存在，生命周期贯穿整个程序
- BSS 段在程序加载时被操作系统自动清零——所以全局数组默认值全是 0
- 它不占用栈空间，不会因为数组太大导致栈溢出
5.3 全局 vs 局部的选择
| 场景 | 推荐 | 原因 |
|---|---|---|
| 小型教学程序 | 全局数组 | 简洁，无需传参 |
| 模块化设计 | 局部数组 | 封装性好，避免意外修改 |
| 多文件项目 | static 全局 | 文件作用域限制，避免命名冲突 |
| 大型数组（>1MB） | 全局或 static | 避免栈溢出 |
| 递归函数 | 局部数组 | 每次调用独立的副本 |
// 全局数组：所有函数共享
int global_arr[1000];
void func_a(void) { global_arr[0] = 42; }
void func_b(void) { printf("%d\n", global_arr[0]); } // 能看到 42
// 局部数组：每个函数独立
void func_c(void) {
int local_arr[1000]; // 在 func_c 的栈帧中
local_arr[0] = 42;
}
void func_d(void) {
int local_arr[1000]; // 在 func_d 的栈帧中，完全不同的数组
printf("%d\n", local_arr[0]); // 未初始化，值是随机的！
}WARNING
局部数组（在函数内部声明的数组）如果不初始化，其元素值是不确定的（栈上的残留数据）。全局数组和 static 数组则会被自动初始化为 0。这是 C 语言初学者最常见的 bug 来源之一。
6. #define 宏常量与 const 对比
6.1 #define 的工作原理
#define ALL 10
#define OUT 3#define 宏定义的常量在编译之前被预处理器替换为具体值。比如 int next[ALL]; 在编译之前就被改为 int next[10];。
预处理过程：
源代码: 预处理后:
#define ALL 10
int next[ALL]; → int next[10];
for (i=0; i<ALL; i++) → for (i=0; i<10; i++)这种「文本替换」的特性意味着：
- 没有类型信息：
ALL可以被替换到任何需要整数的地方 - 没有作用域：从定义处到文件末尾（或
#undef）一直有效 - 没有地址：不能取
&ALL，因为它不是一个变量
6.2 #define vs const 完整对比
| 特性 | #define ALL 10 | const int ALL = 10; |
|---|---|---|
| 处理阶段 | 预处理期（文本替换） | 编译期（类型检查） |
| 类型安全 | 无类型 | 有类型（const int） |
| 作用域 | 文件作用域（可被 #undef） | 遵循 C 作用域规则 |
| 取地址 | 不可取地址 | 可取地址 &ALL |
| 调试可见 | 不可见（已被替换为字面量） | 可见（有符号名和地址） |
| 数组长度 | ✓ C89/C90 支持 | ✗ C89/C90 不支持（C99 VLA 支持） |
| 内存占用 | 不占内存（编译时替换） | 占用内存（通常放在只读数据段） |
| 条件编译 | 可与 #if 配合 | 不能用于 #if |
6.3 为什么数组长度必须用 #define
在 C89/C90 标准中，数组长度必须是编译时常量（compile-time constant）。const int 在 C89/C90 中不算是编译时常量——它只是「运行时常量」（runtime constant），即在程序运行时其值不可修改，但编译器在编译时无法确定其值。因此：
const int N = 10;
int arr[N]; // C89/C90: 编译错误！N 不是编译时常量
// C99+: 合法（VLA——变长数组）而 #define N 10 在预处理阶段就被替换为字面量 10，编译器看到的是 int arr[10];——这在所有 C 标准中都是合法的。
IMPORTANT
C 语言中定义数组长度必须用 #define（或 enum），因为 C89/C90 标准要求数组长度是编译时常量。const int 在 C89 中不算是编译时常量，不能用作数组长度。
7. 条件编译 #if / #else
7.1 原始 josephus.c 中的条件编译
原始 josephus.c 中用 #if 1 / #else 保留了两种环形遍历的实现：
#if 1
pos = ++pos % ALL_NUM; // 取模法（当前启用的版本）
step = step % COUNT_NUM;
#else
pos++; // if 判断法（保留备选）
if (pos == ALL_NUM)
pos = 0;
if (step == COUNT_NUM)
step = 0;
#endif#if 1 表示「始终编译这个分支」。如果改成 #if 0，则切换到另一分支。这是在开发过程中保留两种实现备选的常见做法——不需要注释掉大段代码，只需改一个数字。
7.2 #if 与 if 的本质区别
#if 1 / #else | if (x) / else | |
|---|---|---|
| 处理阶段 | 预处理期（编译前） | 运行期（程序运行时） |
| 决策依据 | 编译时已知的常量表达式 | 运行时变量值 |
| 代码生成 | 不编译未选中的代码 | 两个分支都进入可执行文件 |
| 性能代价 | 零运行时代价 | 每次执行都要分支判断 |
| 用途 | 编译时选择实现、平台适配 | 运行时条件判断 |
条件编译的核心价值：它是「编译时」而非「运行时」的选择——被排除的分支根本不会生成机器码，零执行代价。这在以下场景中非常有用：
- 调试版本 vs 发布版本（
#if DEBUG） - 不同平台的适配代码（
#if __linux__） - 算法变体的 A/B 测试
7.3 条件编译的更多用法
#define METHOD 1 // 在文件顶部切换算法
#if METHOD == 1
// 链表跳转法
#define ALGO_NAME "linked-list skip"
#elif METHOD == 2
// 标志删除法
#define ALGO_NAME "flag deletion"
#else
// 数学递推法
#define ALGO_NAME "recurrence formula"
#endif7.4 if 判断 vs 取模的性能讨论
课堂讨论中问「if 和直接赋值哪种效率高？」这本质上是一个分支预测问题（回顾 Lesson 04 中的讨论）：
// 方案 A: 直接赋值（无分支，有除法）
pos = ++pos % ALL_NUM;
// 方案 B: if 判断（有分支，无除法）
pos++;
if (pos == ALL_NUM)
pos = 0;- 方案 A：每次都要执行
idiv（整数除法）指令，成本较高（约 20-40 周期），但无分支 - 方案 B：只有递增和比较跳转指令，成本低（通常 1-2 周期），但
pos == ALL_NUM只有 1/n 的概率为真——分支预测命中率接近 100%，性能通常更好
在约瑟夫环场景下（n 较大时），方案 B 通常更快。但现代编译器在 -O2 下会把方案 A 中的 % n 优化为条件移动指令 cmov（当 n 不是 2 的幂时仍可能有除法），或把方案 B 的 if 也优化为 cmov，达到无分支效果。
TIP
课堂讨论这个问题的意义不在于「选择哪个更快」——而在于理解代码的底层实现，培养性能分析的意识。在绝大多数实际场景中，两种写法的性能差异可以忽略，选择更清晰易读的写法即可。
8. 计数器状态机设计
8.1 约瑟夫环中的状态机
约瑟夫环的淘汰循环本质上是一个有限状态机（Finite State Machine）：
counter++ counter == OUT
┌───────────┐ counter++ ┌────────────┐
│ COUNTING │──────────────▶│ ELIMINATE │
│ (计数中) │ │ (淘汰中) │
└───────────┘ └─────┬──────┘
▲ │
│ counter = 0 │
└─────────────────────────────┘
(淘汰后重置计数器)状态机有两个状态：
- COUNTING（计数中）：
counter从 1 递增到OUT-1，每次迭代counter++ - ELIMINATE（淘汰中）：
counter == OUT时触发，执行删除操作后counter = 0回到 COUNTING
8.2 计数器变量的生命周期
int counter = 0; // 初始为 0
while (left > 0)
{
counter++; // 每次迭代递增
if (counter == OUT) // 达到淘汰阈值
{
// 执行淘汰操作
counter = 0; // 重置计数器 ← 关键！
}
// ...
}counter 在两种情况下被修改：
- 递增：每次循环体开始，无条件
counter++ - 重置：当
counter == OUT时，counter = 0
这个看似简单的计数器，实际上是一个带有复位逻辑的累加器——它模拟了「数 1, 2, 3, 1, 2, 3, ...」的周期行为。
8.3 状态机的泛化
计数器状态机模式可以泛化到许多场景：
// 模式：周期性触发事件
int tick = 0;
while (condition) {
tick++;
if (tick == THRESHOLD) {
do_periodic_action(); // 每 THRESHOLD 步触发一次
tick = 0;
}
}这种模式在嵌入式系统（定时器中断）、游戏开发（帧计数）、网络协议（心跳包）中随处可见。约瑟夫环的计数器状态机是这些复杂系统的最简雏形。
9. 数据驱动编程：从 Rob Pike 的格言出发
9.1 数据结构先于算法
翻阅 README 中的名人名言，Rob Pike（Go 语言之父，和 Ken Thompson 一起设计了 UTF-8 编码格式，现 Google 首席工程师）说：
"Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming."
"数据压倒一切。如果已经选择了正确的数据结构并且把一切都组织得井井有条，正确的算法也就不言自明。编程的核心是数据结构，而不是算法。"
在约瑟夫环中，这个思想体现得淋漓尽致：
- 用
next[]数组替代链表指针：数据结构变了（从 struct 链表变成 int 数组），但算法的逻辑结构不变（环形遍历 + 节点删除） - 用
(i+1) % n替代条件判断：用数学性质消除了边界检查，环形结构从「if 判断」变成了「数学运算」 - 用
next[prev] = next[i]替代标志置零：删除的语义从「标记为无效」变为「从结构中移除」，算法更简洁
9.2 两种数据结构的算法演化
数据结构: people[] 数组（存储编号，标记删除）
↓
算法: 扫描数组 → 检查是否存活 → 计数 → 标记为 0
↓
问题: 无效位置越来越多，扫描越来越慢
数据结构: next[] 数组（存储下一人位置，链表跳转）
↓
算法: next[prev] = next[i] → i = next[i] → counter++
↓
结果: 每次迭代都处理有效节点，O(n*m) 复杂度核心启示：当你觉得算法变得复杂难懂，回到数据结构层面重新审视——也许换个结构就能让算法「不言自明」。
9.3 Pike 的第三句名言
Rob Pike 还有一句更直白的表述：
"给我看流程图而不让我看（数据）表，我仍会茫然不解；如果给我看（数据）表，通常就不需要流程图了；数据表足够说明问题了。"
在约瑟夫环中，next[] 数组本身就是一张「数据表」——它记录了环中每个人的下一人是谁。有了这张表，出局的流程自然浮现：找到出局者，让他的前驱跳过他。不需要画流程图，数据结构本身就描述了算法。
10. 数学递推公式
10.1 递推公式的推导
标志删除法和链表跳转法都是「模拟」——一步步复现约瑟夫环的淘汰过程。但数学上，我们可以直接计算幸存者的位置，无需模拟。
递推公式：
f(1) = 0
f(n) = (f(n-1) + m) % n (n > 1)其中 f(n) 表示 n 个人、每 m 个淘汰时，幸存者的 0-based 编号。
10.2 公式的含义
f(n) = (f(n-1) + m) % n 的含义是：
如果你已经知道 n-1 个人时的幸存者位置是
f(n-1)，那么加入第 n 个人（编号 n-1）后，新幸存者的位置就是在f(n-1)的基础上向后偏移 m 步，然后对 n 取模。
这是因为：当第一个人（从 0 开始数到 m-1）出局后，问题退化为 n-1 个人的约瑟夫环——但编号需要重新映射。
10.3 手动推导示例
m=3 时:
f(1) = 0 → 1人中，第0号幸存
f(2) = (f(1) + 3) % 2 = (0+3) % 2 = 1
→ 2人中，第1号幸存
验证: [0,1], 数到3 → 0出局(3%2=1, 即第1个), 1幸存 ✓
f(3) = (f(2) + 3) % 3 = (1+3) % 3 = 1
→ 3人中，第1号幸存
验证: [0,1,2], 数到3 → 2出局, 数到3 → 0出局, 1幸存 ✓
f(4) = (f(3) + 3) % 4 = (1+3) % 4 = 0
→ 4人中，第0号幸存
f(5) = (f(4) + 3) % 5 = (0+3) % 5 = 3
→ 5人中，第3号幸存
验证: [0,1,2,3,4], 淘汰顺序 2→0→4→1, 3幸存 ✓10.4 递推公式的代码实现
// 递推公式实现——O(n) 时间，O(1) 空间
int josephus(int n, int m)
{
int f = 0;
int i;
for (i = 2; i <= n; i++)
f = (f + m) % i;
return f; // f 是幸存者的 0-based 位置
}这是约瑟夫环问题的最优解：O(n) 时间，O(1) 额外空间。不需要任何数组，不需要模拟淘汰过程——纯数学计算。
10.5 三种方法的完整对比
| 方法 | 时间复杂度 | 空间复杂度 | 能得到出局顺序？ | 核心思想 |
|---|---|---|---|---|
| 标志删除法 | O(n²) | O(n) | ✓ | 数组标记 + 线性扫描 |
| 链表跳转法 | O(n*m) | O(n) | ✓ | next[] 数组模拟链表 |
| 递推公式法 | O(n) | O(1) | ✗（仅幸存者） | 数学归纳 |
NOTE
递推公式只给出最终幸存者位置，不能给出完整的出局顺序。如果需要打印每个人的出局顺序（如本课练习 2），仍需要用链表模拟。数学解法体现了「不同问题需要不同工具」的原则——不是所有场景下数学推导都能替代模拟。
10.6 约瑟夫斯问题的真实答案
回到历史：约瑟夫斯和 40 名战友（n=41），每数到第 3 人（m=3）：
f(41) = ?
用递推公式:
f(1)=0 → f(2)=1 → f(3)=1 → ... → f(41)=300-based 位置 30，即 1-based 位置 31。约瑟夫斯站在第 31 号位置（倒数第二），他的朋友站在第 16 号位置——两人幸存。
11. XOR 交换
11.1 传统交换 vs XOR 交换
在约瑟夫环的实现中我们不需要交换操作，但本课的课后练习（奇偶排序）涉及元素交换。这里介绍一种有趣的替代方案：
// 传统交换（需要临时变量）
int tmp = a;
a = b;
b = tmp;
// XOR 交换（无需临时变量）
a = a ^ b;
b = a ^ b;
a = a ^ b;11.2 XOR 交换的原理
XOR（异或）运算满足以下性质：
x ^ x = 0（自反性）x ^ 0 = x（恒等性）- 交换律：
a ^ b = b ^ a - 结合律：
(a ^ b) ^ c = a ^ (b ^ c)
利用这些性质，XOR 交换的推导过程：
初始: a=A, b=B
第一步: a = A ^ B (a 现在存储了 A 和 B 的异或)
第二步: b = (A ^ B) ^ B = A ^ (B ^ B) = A ^ 0 = A
(b 变成了原来的 a)
第三步: a = (A ^ B) ^ A = (A ^ A) ^ B = 0 ^ B = B
(a 变成了原来的 b)
最终: a=B, b=A —— 完成交换11.3 XOR 交换的注意事项
CAUTION
XOR 交换有一个致命陷阱：如果 a 和 b 是同一个变量（即 &a == &b），第一步 a = a ^ a = 0，之后无论怎么操作结果都是 0——数据被清零了！
// 危险！如果 i == j，arr[i] 被清零
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];因此，在现代编程实践中，XOR 交换更多是一种智力游戏而非实用技巧。使用 tmp 变量的传统交换更安全、更清晰，编译器也会优化掉临时变量。
12. struct 方案 vs 数组方案
12.1 用 struct 重新实现约瑟夫环
如果我们使用传统的 struct 链表，约瑟夫环的实现如下：
#include <stdio.h>
#include <stdlib.h>
struct Node {
int id;
struct Node *next;
};
int main(void)
{
int n = 10, m = 3;
struct Node *head, *prev, *cur;
int i;
// 创建循环链表
head = malloc(sizeof(struct Node));
head->id = 1;
prev = head;
for (i = 2; i <= n; i++) {
cur = malloc(sizeof(struct Node));
cur->id = i;
prev->next = cur;
prev = cur;
}
prev->next = head; // 形成闭环
// 约瑟夫环淘汰
cur = head;
prev = NULL; // 需要单独跟踪前驱
int left = n;
int counter = 0;
while (left > 0) {
counter++;
if (counter == m) {
printf("%d is out\n", cur->id);
prev->next = cur->next;
free(cur); // 需要手动释放内存
cur = prev->next;
left--;
counter = 0;
} else {
prev = cur;
cur = cur->next;
}
}
return 0;
}12.2 两种方案的深度对比
| 维度 | struct 链表 | next[] 数组 |
|---|---|---|
| 头文件依赖 | #include <stdlib.h>（malloc/free） | 无额外依赖 |
| 创建节点 | malloc 逐个分配 | 数组声明一次性分配 |
| 节点标识 | cur->id（显式存储） | 数组下标 i（隐式标识） |
| 删除节点 | free(cur)（手动回收） | 自动回收（数组生命周期管理） |
| 内存泄漏风险 | 有（忘记 free） | 无 |
| 空指针风险 | 有（NULL 解引用） | 无 |
| 代码行数 | ~30 行 | ~20 行 |
| 灵活性 | 可动态增减节点 | 编译时固定大小 |
| 教学重点 | 指针、malloc、内存管理 | 下标模拟、取模、逻辑抽象 |
12.3 为什么入门阶段用数组方案
next[] 数组方案将「指针」的语义隐藏在「下标」背后。学生在理解 next[prev] = next[i] 时，实际上在理解链表删除的核心逻辑——当后续课程引入真正的 struct 链表时，学生只需要把 next[i] 换成 cur->next，把 i 换成 *cur，逻辑结构完全一致。
这是一种「延迟复杂性」的教学策略——先让学生掌握环形数据结构 + 链表删除的逻辑，再引入指针语法的实现细节。
13. 循环缓冲区
13.1 从约瑟夫环到循环缓冲区
约瑟夫环中的 next[] 数组本质上是一个循环数据结构。这个结构在计算机科学中有一个更通用的名字：循环缓冲区（Circular Buffer / Ring Buffer）。
循环缓冲区的结构:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
↑ ↑
head (读指针) tail (写指针)
head = 0, tail = 3 → 缓冲区中有 3 个元素循环缓冲区是一个固定大小的环形队列：当 tail 到达数组末尾时，通过取模绕回起点，覆盖最旧的数据。
13.2 循环缓冲区的核心操作
#define BUF_SIZE 8
int buf[BUF_SIZE];
int head = 0; // 读位置
int tail = 0; // 写位置
int count = 0; // 当前元素数
// 写入一个元素
void enqueue(int val) {
if (count < BUF_SIZE) {
buf[tail] = val;
tail = (tail + 1) % BUF_SIZE; // 取模绕回
count++;
}
}
// 读取一个元素
int dequeue(void) {
int val = -1;
if (count > 0) {
val = buf[head];
head = (head + 1) % BUF_SIZE; // 取模绕回
count--;
}
return val;
}13.3 循环缓冲区的应用场景
| 场景 | 说明 |
|---|---|
| 操作系统内核 | 键盘输入缓冲区、管道（pipe）实现 |
| 网络协议栈 | TCP 滑动窗口、网卡收发队列 |
| 音视频处理 | 音频采样缓冲区、视频帧队列 |
| 嵌入式系统 | UART 串口收发缓冲、传感器数据采集 |
| 日志系统 | 固定大小环形日志（最旧日志自动覆盖） |
13.4 从约瑟夫环到轮转调度
操作系统的轮转调度（Round-Robin Scheduling）正是约瑟夫环的直接应用：n 个进程围成一个圈，每个进程获得固定时间片（time slice），时间片用完就轮到下一个进程。next[i] = (i + 1) % n 就是调度器的核心逻辑——CPU 在进程之间循环切换。
// 简化的轮转调度
int current_process = 0;
int num_processes = N;
int time_slice = 100; // ms
while (1) {
run_process(current_process, time_slice);
current_process = (current_process + 1) % num_processes; // 下一个进程
}约瑟夫环不是一道孤立的编程题——它背后的环形数据结构思想，贯穿了从操作系统内核到嵌入式系统的整个计算机科学领域。
参考解答
练习1: init_ring & print_ring（初始化循环链表）
#include <stdio.h>
#define MAX 1000
int next[MAX];
int n;
void init_ring(void)
{
int i;
for (i = 0; i < n; i++)
next[i] = (i + 1) % n;
}
void print_ring(void)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", next[i]);
printf("\n");
}
int main(void)
{
scanf("%d", &n);
init_ring();
print_ring();
return 0;
}核心：next[i] = (i + 1) % n 建立闭环——最后一个人 n-1 的 next 指向 0，形成循环结构。print_ring 打印所有 next 值以验证初始化正确。注意每个数字后跟一个空格（包括最后一个数字），最后输出换行符。
练习2: 约瑟夫环链表跳转法（ALL=10, OUT=3）
#include <stdio.h>
#define ALL 10
#define OUT 3
int next[ALL];
void init_ring(void)
{
int i;
for (i = 0; i < ALL; i++)
next[i] = (i + 1) % ALL;
}
int main(void)
{
int left = ALL;
int counter = 0;
int i = 0;
int prev = ALL - 1;
init_ring();
while (left > 0)
{
counter++;
if (counter == OUT)
{
printf("%d is out\n", i + 1);
next[prev] = next[i];
left--;
counter = 0;
}
else
{
prev = i;
}
i = next[i];
}
return 0;
}核心逻辑：counter 每走一步加 1，当 counter == OUT 时触发淘汰。出局者通过 next[prev] = next[i] 从链表中跳过。prev 只在正常情况下更新（被淘汰时 prev 保持不变，因为被淘汰者不能作为前驱）。初始 prev = ALL-1 是因为链表是环形的，第一个人的前驱就是最后一个人。
标志删除法（原始 josephus.c 方案）
#include <stdio.h>
#define ALL_NUM 100
#define COUNT_NUM 3
#define OUT_NUM 3
int people[ALL_NUM];
int main(void)
{
int left = ALL_NUM;
int pos = 0;
int step = 0;
int i;
for (i = 0; i < ALL_NUM; i++)
people[i] = i + 1;
while (left > 0)
{
if (people[pos] > 0)
step++;
if (step == OUT_NUM && people[pos] != 0)
{
printf("%d out \n", people[pos]);
people[pos] = 0;
left--;
}
pos = ++pos % ALL_NUM;
step = step % COUNT_NUM;
}
return 0;
}标志删除法中 people[pos] = 0 标记出局。每次迭代不管当前位置是否有效都向下推进——无效位置越多，浪费的迭代次数越多。链表跳转法（练习 2）正好弥补了这一缺陷。注意条件编译 #if 1 / #else 的使用——保留了两种环形前进方式的备选实现。
对照检查：
next[i] = (i + 1) % n写对了吗？prev初始值是ALL - 1吗？出局时next[prev] = next[i]而非next[i + 1]吗？counter出局后是否重置为 0？
课堂讨论
pos和step变量，每次赋值用if和直接用取模%，在执行效率上有什么不同？- 在标志删除法中，留在环里面的人越少，无效的比较次数越多——有什么办法可以优化算法？
- 如何使用数组实现链表跳转法的优化？链表跳转法的核心改进点在哪里？
- 约瑟夫环问题有一个递推公式：
f(1) = 0; f(n) = (f(n-1) + m) % n。试分析这个公式和链表模拟法之间的关系。 - 如果约瑟夫环要求逆时针方向计数（即从当前位置向左数），如何修改代码？
- 在约瑟夫环中，如果每次淘汰的不是第 m 个人，而是第 m 个存活的人（跳过已出局者），标志删除法和链表跳转法的实现分别需要如何修改？
讨论答案
Q1: if 判断 vs 取模 % 的执行效率差异
核心差异：分支预测 vs 整数除法。
// 方案 A: 取模（有 div 指令）
pos = ++pos % ALL_NUM;
// 方案 B: if 判断（有分支跳转）
pos++;
if (pos == ALL_NUM)
pos = 0;| 层面 | 方案 A（取模） | 方案 B（if 判断） |
|---|---|---|
| 机器指令 | idiv（整数除法，20-40 周期） | cmp + jne（比较跳转，1-2 周期） |
| 分支预测 | 无分支，确定执行 | pos==ALL_NUM 概率 1/n，几乎总能正确预测 |
| 代码体积 | 1 条指令 | 3-4 条指令 |
| 编译器优化 | -O2 下可能被优化为乘法+移位 | -O2 下可能改为 cmov（条件移动） |
对于约瑟夫环（n 较大时），if 判断通常更快——分支预测几乎从来不错。但现代编译器在 -O2 下会优化掉两者的差异。结论：优先考虑可读性，不必为了这个级别的差异而牺牲代码清晰度。真正的性能瓶颈通常在 I/O 和算法复杂度上，而不是这种微优化。
更深层的思考：当 n 是 2 的幂（如 8、16、32）时，编译器可以将 % n 优化为 & (n-1)（按位与），此时取模方案反而比 if 判断更快。这是编译器优化的一个经典案例。
Q2: 标志删除法的无效比较如何优化？
标志删除法的核心问题是随着淘汰者增多，遍历到有效人的概率越来越小。
第 1 个人出局后: 1/100 的位置无效 → 平均 1.01 次迭代找到下一个有效人
第 50 个人出局后: 50/100 的位置无效 → 平均 2 次迭代
第 90 个人出局后: 90/100 的位置无效 → 平均 10 次迭代
第 99 个人出局后: 99/100 的位置无效 → 平均 100 次迭代！优化方案一：链表跳转法——用 next[] 数组记录「下一个有效人的位置」，让遍历总是直接跳到有效位置。这是本课的核心优化。
优化方案二：惰性跳过（Lazy Skip）。当 people[pos] == 0 时，连续向前扫描直到找到有效人：
while (people[pos] == 0)
pos = (pos + 1) % n;虽然仍比链表法慢（每次找到有效人后还要再数 m-1 步），但避免了在无效位置上的计数和比较迭代。
优化方案三：压缩数组。每次出局后，将数组末尾的有效元素移到出局位置，然后缩小有效范围。这种方法改变了元素的相对顺序，但减少了无效位置的产生。
Q3: 链表跳转法如何用数组实现？核心改进是什么？
链表跳转法的数组实现已在练习 2 中展示。核心改进有两点：
改进 1：跳转的效率
// 标志法——每次都要逐一扫描找下一个有效人
i = (i + 1) % n; // 可能踩到无效位置
// 链表法——总是跳到下一个有效人
i = next[i]; // 100% 有效改进 2：删除的语义
// 标志法——标记为「已死」，但保留在数组中
people[pos] = 0;
// 链表法——物理上从链中移除
next[prev] = next[i]; // prev 跳过 i，i 从链中消失本质区别：标志法保留了死节点的所有数据结构代价（仍需遍历），链表法彻底解除了死节点与结构的耦合——删除了就不再访问。
更进一步的理解：标志法中的数组既是「容器」又是「逻辑结构」，两者耦合在一起。链表法将它们分离——数组是容器（存储 next 值），而 next 值自身定义了一个独立的逻辑结构（链表）。这种「数据与结构分离」的思想是数据结构设计的核心原则之一。
Q4: 递推公式 f(n) = (f(n-1) + m) % n 与链表模拟的关系
这是约瑟夫环问题的数学优雅解。
递推公式：f(1) = 0; f(n) = (f(n-1) + m) % n
含义：n 个人中的幸存者位置 = 在 n-1 个人中的幸存者位置基础上，加上 m 步偏移，然后对 n 取模。
推导思路：
- n 个人的环，第一次淘汰的是编号为
(m-1) % n的人 - 淘汰后剩下 n-1 个人，但编号需要重新映射
- 旧编号 k 映射为新编号
(k - m) % n（取模保证在 0~n-2） - 反过来说，n-1 人环中的幸存者编号
f(n-1)，映射回 n 人环中的编号为(f(n-1) + m) % n
m=3 时:
f(1) = 0 → 1人中，第0号幸存
f(2) = (0+3) % 2 = 1 → 2人中，第1号幸存
f(3) = (1+3) % 3 = 1 → 3人中，第1号幸存
f(4) = (1+3) % 4 = 0 → 4人中，第0号幸存
f(5) = (0+3) % 5 = 3 → 5人中，第3号幸存链表模拟 vs 递推公式：
- 链表模拟：直接复现历史场景，时间复杂度 O(n*m)，能得到完整出局顺序
- 递推公式：数学归纳分析，时间复杂度 O(n)，只能得到最终幸存者位置
递推公式不依赖任何数据结构——只用整数计算。这是数据结构和算法之间的典型张力：有时一个好的数学分析能完全替代复杂的结构实现。
// 递推公式实现（最简洁的约瑟夫环解法）
int josephus(int n, int m)
{
int f = 0;
int i;
for (i = 2; i <= n; i++)
f = (f + m) % i;
return f; // f 是幸存者的 0-based 位置
}NOTE
递推公式只给出最终幸存者位置，不能给出完整的出局顺序。如果需要打印每个人的出局顺序（如本课练习 2），仍需要用链表模拟。
Q5: 逆时针方向计数如何修改？
逆时针方向意味着每次向前（prev 方向）移动而不是向后（next 方向）。这需要修改两个地方：
方法一：建立双向链表
int next[ALL]; // 顺时针的下一个
int prev[ALL]; // 逆时针的下一个（即顺时针的前一个）
// 初始化
for (i = 0; i < ALL; i++) {
next[i] = (i + 1) % ALL;
prev[i] = (i - 1 + ALL) % ALL; // 注意处理负数取模
}
// 遍历时使用 prev 而不是 next
i = prev[i];方法二：修改 next 数组的初始化方向
// 让 next[i] 指向逆时针方向的下一个人
for (i = 0; i < ALL; i++)
next[i] = (i - 1 + ALL) % ALL;这样 i = next[i] 就是逆时针移动，其余淘汰逻辑完全不变。
关键点：在 C 语言中，(-1) % ALL 的结果是负数（C89/C90 中行为是实现定义的，C99 后规定向零取整）。因此必须写成 (i - 1 + ALL) % ALL 来确保结果为正。这是一个容易被忽略的边界情况。
Q6: 淘汰第 m 个存活的人时两种方法的修改
标志删除法：基本不需要修改！因为标志删除法已经通过 if (people[pos] > 0) 跳过了已出局者，step++ 只对存活的人计数。所以「数到第 m 个存活的人」就是当前的行为。
链表跳转法：同样不需要修改！因为链表跳转法中 i = next[i] 总是跳到下一个存活的人，counter 自然也只对存活的人计数。
这个问题的答案是：链表跳转法天然就是淘汰第 m 个存活的人，因为链表中不存在已出局者。而标志删除法需要显式的 if (people[pos] > 0) 判断来跳过。两种方法对「存活」的定义不同：
- 标志法：存活 =
people[pos] != 0（显式检查） - 链表法：存活 = 在链表中存在（隐式保证）
这再次验证了「数据结构选择决定算法复杂度」的原则——链表法中「只遍历存活者」不是算法技巧，而是数据结构的自然结果。
课后练习
统计比较次数：在标志删除法的程序中增加一个计数器，统计在执行过程中
if (people[pos] > 0)总共执行了多少次（含对无效位置的检查）。用ALL_NUM=100测试。知识点提示：计数器变量、循环内累计、
#define宏常量的单点修改万年历打印：已知 2012 年 1 月 1 日是星期日，打印出 2012 年全年的月历（12 个月，每个 7 列）。要求用函数、数组和循环组织代码。
知识点提示：用数组存储每月天数、闰年判断、
\n和\t格式化对齐、循环遍历 12 个月奇偶排序：用户输入 10 个数字，将它们重新排列，使所有奇数排在前面，所有偶数排在后面。
知识点提示：双指针交换、分类而非全排序、就地重排算法
数学递推法实现：编写一个函数
int josephus(int n, int m)，使用递推公式f(n) = (f(n-1) + m) % n计算并返回幸存者的 1-based 编号。在main中读入 n 和 m，输出结果。对比与链表模拟法的运行结果是否一致。知识点提示：递推公式、函数封装、O(n) vs O(n*m) 复杂度对比
循环缓冲区实现：实现一个固定大小为 8 的循环缓冲区，支持
enqueue（入队）和dequeue（出队）操作。当缓冲区满时，新的入队操作覆盖最旧的数据。用取模实现环形索引。知识点提示：取模绕回、head/tail 指针管理、满/空条件判断、覆盖策略
练习1: 统计标志删除法的比较次数
#include <stdio.h>
#define ALL_NUM 100
#define COUNT_NUM 3
#define OUT_NUM 3
int main(void)
{
int people[ALL_NUM];
int left = ALL_NUM;
int pos = 0;
int step = 0;
int comparisons = 0; // 新增：比较次数计数器
int i;
for (i = 0; i < ALL_NUM; i++)
people[i] = i + 1;
while (left > 0)
{
if (people[pos] > 0)
{
comparisons++; // 计数：这次的 if 检查有效
step++;
}
else
comparisons++; // 计数：这次的 if 检查也执行了（只是结果为假）
if (step == OUT_NUM && people[pos] != 0)
{
printf("%d out \n", people[pos]);
people[pos] = 0;
left--;
}
pos = ++pos % ALL_NUM;
step = step % COUNT_NUM;
}
printf("total comparisons = %d\n", comparisons);
return 0;
}运行后 total comparisons 的值远大于 ALL_NUM（100），因为标志法需要遍历许多无效位置。可以对比链表跳转法——后者只需约 ALL_NUM * OUT_NUM 次迭代，且每次迭代都对应一个有效人。
练习2: 万年历打印（核心逻辑）
#include <stdio.h>
int is_leap(int year)
{
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
int main(void)
{
int year = 2012;
int month_days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int start_day = 0; // 2012-01-01 is Sunday (0)
int m, d;
if (is_leap(year))
month_days[1] = 29;
for (m = 0; m < 12; m++)
{
printf("Month %d\n", m + 1);
printf("Sun Mon Tue Wed Thu Fri Sat\n");
for (d = 0; d < start_day; d++)
printf(" "); // 月初空白
for (d = 1; d <= month_days[m]; d++)
{
printf("%3d ", d);
if ((start_day + d) % 7 == 0)
printf("\n");
}
printf("\n\n");
start_day = (start_day + month_days[m]) % 7;
}
return 0;
}核心：用数组存储每月天数，用取模 % 7 计算星期几。start_day 记录每月 1 号是星期几，月初先输出空白填充。(start_day + d) % 7 == 0 在逢 7 时换行。注意闰年 2 月有 29 天。
练习3: 奇偶排序（双指针交换）
#include <stdio.h>
int main(void)
{
int arr[10];
int i = 0, j = 9;
int k;
for (k = 0; k < 10; k++)
scanf("%d", &arr[k]);
while (i < j)
{
while (i < j && arr[i] % 2 == 1)
i++; // i 停在偶数上
while (i < j && arr[j] % 2 == 0)
j--; // j 停在奇数上
if (i < j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp; // 交换：奇数→前，偶数→后
}
}
for (k = 0; k < 10; k++)
printf("%d ", arr[k]);
printf("\n");
return 0;
}双指针：i 从左向右找偶数（需要移到后面的），j 从右向左找奇数（需要移到前面的），交换它们。算法终止时 i >= j。这不是完整排序，只是「分类重排」——时间复杂度 O(n)，比完整排序 O(n log n) 更高效。
练习4: 数学递推法实现
#include <stdio.h>
int josephus(int n, int m)
{
int f = 0;
int i;
for (i = 2; i <= n; i++)
f = (f + m) % i;
return f + 1; // 转换为 1-based 编号
}
int main(void)
{
int n, m;
scanf("%d %d", &n, &m);
printf("Survivor: %d\n", josephus(n, m));
return 0;
}递推公式 f(n) = (f(n-1) + m) % n 以 O(n) 时间和 O(1) 空间直接计算幸存者位置。f(1)=0 是边界条件，循环从 i=2 开始递推到 i=n。返回时 f+1 将 0-based 转换为 1-based 编号。可以输入 n=10, m=3 验证：输出应为 4（与链表模拟法结果一致）。
练习5: 循环缓冲区实现
#include <stdio.h>
#define BUF_SIZE 8
int buf[BUF_SIZE];
int head = 0;
int tail = 0;
int count = 0;
void enqueue(int val)
{
buf[tail] = val;
tail = (tail + 1) % BUF_SIZE;
if (count < BUF_SIZE)
count++;
else
head = (head + 1) % BUF_SIZE; // 满时覆盖最旧的
}
int dequeue(void)
{
int val;
if (count == 0) return -1; // 空队列
val = buf[head];
head = (head + 1) % BUF_SIZE;
count--;
return val;
}
void print_buf(void)
{
int i;
printf("Buffer: ");
for (i = 0; i < count; i++)
printf("%d ", buf[(head + i) % BUF_SIZE]);
printf("\n");
}
int main(void)
{
int i;
for (i = 1; i <= 10; i++) {
enqueue(i);
print_buf();
}
for (i = 0; i < 5; i++) {
printf("Dequeued: %d\n", dequeue());
print_buf();
}
return 0;
}循环缓冲区的核心是 (index + 1) % BUF_SIZE 实现环形索引。当 count == BUF_SIZE（满）时，新元素覆盖最旧数据，head 前移。print_buf 从 head 开始遍历 count 个元素，用 (head + i) % BUF_SIZE 计算实际索引。这个实现展示了约瑟夫环中取模技术的实际工程应用。
参考资料
- Josephus Problem - Wikipedia — 约瑟夫环问题的历史、变体与递推解法，包含 n=41, m=3 的历史真实答案
- Rob Pike: Notes on Programming in C — Rob Pike 的 C 语言编程哲学（数据结构驱动编程思想）
- GNU C Preprocessor: Conditionals —
#if/#else/#elif条件编译的完整文档 - ISO C99 Standard, Section 6.5.5 — 取模运算符
%的语义定义（向零取整行为） - Circular Buffer - Wikipedia — 循环缓冲区的形式化定义、实现方法和应用场景
"Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident." — Rob Pike