当前位置：首页 > news >正文

用C语言模拟‘击鼓传花’：PTA习题8-4报数游戏两种解法详解（附完整代码）

news 2026/4/16 10:46:10

用C语言模拟‘击鼓传花’：PTA习题8-4报数游戏两种解法详解（附完整代码）

在编程学习的道路上，算法题常常让人望而生畏。但如果我们换个角度，把算法问题想象成生活中的游戏，一切就会变得有趣起来。PTA习题8-4的报数游戏，本质上就是一个经典的"击鼓传花"问题——一群人围成一圈，按特定规则依次退出，直到最后一人留下。本文将带你用C语言实现这个游戏，并深入分析两种不同的解决思路。

1. 问题理解与建模

报数游戏（约瑟夫问题）的规则很简单：n个人围成一圈，从第一个人开始报数，数到m的人退出；然后从下一个人重新开始报数，数到m的人再退出，直到所有人都退出为止。我们需要记录每个人退出的顺序。

这个问题看似简单，但在编程实现时需要考虑几个关键点：

环形结构：虽然C语言没有内置的环形数据结构，但我们可以用数组配合取模运算来模拟
状态标记：需要跟踪哪些人已经退出，哪些人仍在游戏中
边界条件：特别注意数组索引的处理，避免越界访问

#define MAXN 1000 // 假设最多1000人参与游戏 void CountOff(int n, int m, int out[]);

2. 标记法实现解析

第一种解法采用"标记法"，思路直观：用一个额外数组记录每个人的状态（是否已退出），然后循环遍历这个数组，直到所有人都退出。

2.1 核心代码实现

void CountOff(int n, int m, int out[]) { int remaining = n; // 剩余人数 int count = 0; // 当前报数 int sequence = 1; // 退出序号 int status[MAXN]; // 状态数组 // 初始化：所有人都未退出 for(int i=0; i<n; i++) { status[i] = 1; // 1表示在圈内 } while(remaining > 0) { for(int i=0; i<n; i++) { if(status[i]) { // 如果人在圈内 count++; if(count == m) { // 报到m的人退出 status[i] = 0; // 标记为已退出 out[i] = sequence++; count = 0; remaining--; } } } } }

2.2 关键点分析

状态数组：status数组记录每个人是否仍在游戏中（1表示在，0表示已退出）
双重循环：外层while控制游戏是否继续，内层for遍历所有人
计数重置：每当有人退出时，将count重置为0，从下一个人重新开始报数

注意：这种方法在n较大时效率不高，因为需要多次完整遍历数组

3. 计数法实现解析

第二种解法更为巧妙，我们称之为"计数法"。它不需要额外的状态数组，而是直接在输出数组上进行操作，通过计数来确定下一个退出的人。

3.1 核心代码实现

void CountOff(int n, int m, int out[]) { int count = 0; // 当前报数 int sequence = 1; // 退出序号 int pos = 0; // 当前位置 // 初始化：所有人都未分配退出序号 for(int i=0; i<n; i++) { out[i] = 0; } while(sequence <= n) { if(out[pos] == 0) { // 如果该位置的人未退出 count++; if(count == m) { // 报到m的人退出 out[pos] = sequence++; count = 0; } } pos = (pos + 1) % n; // 环形移动 } }

3.2 关键点分析

就地操作：直接在out数组上标记，节省了额外空间
环形移动：pos = (pos + 1) % n确保索引在0到n-1之间循环
单次遍历：不需要完整遍历数组，效率更高

提示：这种方法在处理大规模数据时性能更优，但逻辑稍复杂

4. 两种方法的对比与选择

为了更清晰地理解两种方法的差异，我们通过下表进行对比：

特性	标记法	计数法
空间复杂度	O(n)（需要额外状态数组）	O(1)（就地操作）
时间复杂度	O(n×m)（最坏情况）	O(n×m)（但实际更快）
代码复杂度	简单直观	较复杂，需要理解环形移动
适用场景	n较小，代码可读性优先	n较大，性能优先

在实际编程练习中，建议初学者先掌握标记法，理解问题本质后再尝试计数法。对于PTA这类在线评测系统，两种方法都能通过测试，但计数法在大数据量时表现更优。

5. 常见错误与调试技巧

在实现这个算法时，有几个常见的陷阱需要注意：

数组越界：忘记对索引取模是最常见的错误

// 错误示例 pos++; // 可能越界 // 正确做法 pos = (pos + 1) % n;

循环条件错误：使用错误的终止条件可能导致无限循环

// 错误示例 while(1) { /* 可能无法退出 */ } // 正确做法 while(sequence <= n) { /* 明确终止条件 */ }

计数逻辑错误：只在有效位置（未退出的人）才增加计数

// 错误示例 count++; // 没有检查是否已退出 // 正确做法 if(out[pos] == 0) count++;

调试时可以添加临时打印语句，观察程序运行时的变量变化：

printf("pos=%d, count=%d, sequence=%d\n", pos, count, sequence);

6. 完整可运行示例

下面提供一个完整的程序示例，包含主函数和测试用例：

#include <stdio.h> #define MAXN 1000 void CountOff(int n, int m, int out[]) { // 这里插入你选择的方法实现 } int main() { int n, m; int out[MAXN]; printf("输入总人数n和报数m："); scanf("%d %d", &n, &m); CountOff(n, m, out); printf("退出顺序：\n"); for(int i=0; i<n; i++) { printf("%d ", out[i]); } printf("\n"); return 0; }

测试用例示例：