用顺序表实现约瑟夫问题C语言

好的！下面我会详细介绍如何用**顺序表**实现经典的约瑟夫环问题（Josephus Problem），并给出完整的 C 语言代码。 --- ### **什么是约瑟夫问题？** 约瑟夫问题是这样一个场景：有 n 个人围成一圈，从某一个人开始报数，每数到第 m 个人就将这个人移除圈子。然后继续对剩下的人重复这一过程，直到所有人都被移除为止。最终需要输出这些人被移除的顺序。 例如： - 输入：n = 7 （总人数）、m = 3 （每次报数到 3） - 输出：移除顺序为 [3, 6, 2, 7, 5, 1, 4] --- ### **思路分析** 我们可以利用顺序表（数组）模拟这个过程： 1. 初始化一个长度为 n 的数组，表示每个人的状态。 2. 每次找到下一个要移除的人（即满足报数条件的那个人）。 3. 将该人标记为已移除状态，并记录其编号。 4. 继续遍历未移除的人群，重复步骤 2 和 3 直至所有人被移除。 为了高效地找到下一位要移除的人，我们需要维护两个信息： - 当前已经移除了多少人； - 下一轮报数的起始位置。 --- ### **C 实现代码** 以下是完整代码： ```c #include <stdio.h> #define MAX_SIZE 100 // 最大人数限制 void josephus(int n, int m) { if (n <= 0 || m <= 0) return; // 参数校验 int people[MAX_SIZE]; // 数组存储人的状态，初始化全为 1 表示存活 for (int i = 0; i < n; i++) { people[i] = 1; } int count = 0; // 记录当前已移除人数 int index = 0; // 报数起点指针 printf("移除顺序: "); while (count < n) { // 循环直到所有人都被移除 int steps = 0; // 当前轮次的计步器 // 寻找第 m 个人 while (steps < m) { if (people[index] == 1) { // 遇到活着的人才计算一步 steps++; } if (steps == m) break; // 找到目标了 // 移动到下一位置，循环结构 index = (index + 1) % n; } // 标记此人已被移除，并输出序号 people[index] = 0; printf("%d ", index + 1); // 序号从 1 开始 count++; // 准备新一轮查找 do { index = (index + 1) % n; } while (people[index] == 0); // 跳过已经被移除的人 } printf("\n"); } // 主函数测试 int main() { int n = 7, m = 3; // 总人数和间隔值 josephus(n, m); return 0; } ``` --- ### **代码解析** 1. **初始设置** - 定义一个大小为 `MAX_SIZE` 的数组 `people`，用于存储每个人的生存状态 (`1` 表示存活，`0` 表示死亡)。 2. **核心算法** - 使用双层循环： - 外层循环负责控制总共移除 n 个人； - 内层循环通过移动指针寻找第 m 个存活者。 3. **边界处理** - 利用 `(index + 1) % n` 实现循环队列效果，保证越界时回到开头。 4. **优化细节** - 第二层内嵌的 `do...while` 确保新的搜索总是从最近一个活着的人出发，避免浪费时间跳过大量无效数据。 --- ### **运行结果示例** 输入： ``` n = 7, m = 3 ``` 输出： ``` 移除顺序: 3 6 2 7 5 1 4 ``` 这正是预期的结果！ ---