PYTHON LESSON 060
例题精练：击鼓传花谁留下
用队列模拟围圈报数的过程，掌握“队首出列、没到数就回队尾”的循环队列套路。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- pop(0) 队首出列、append() 排到队尾
- while len(queue) > 1 只剩一人时停
- count 归零重新报数
01 · 核心概念
读题→思路→编码→验证：循环队列模拟的经典题（约瑟夫问题）
读题→思路→编码→验证：循环队列模拟的经典题（约瑟夫问题）：题目关键词：围成一圈、依次报数、报到 k 出局、从下一位重新报数。圆圈没有队尾，出列的人回到队伍末尾——这正是在暗示我们用队列：队首出列，没出局就 append 回队尾，队列自己就转成了圈。
GESP Python 4 级 · 队列与循环队列GESP Python 4 级 · 模拟法在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
02 · 语法与规则
先记住这 3 条，再开始写程序
pop(0) 队首出列、append() 排到队尾先准确读出这条写法的结构与作用。
while len(queue) > 1 只剩一人时停换一组最小数据，手工推演一次结果。
count 归零重新报数再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 例题精练：击鼓传花（循环队列 + 模拟）
# 读题：n 人围圈从 1 号开始报数，报到 k 出局，问最后留下谁
n, k = input().split()
n = int(n)
k = int(k)
queue = []
for i in range(1, n + 1):
queue.append(i) # 1~n 号依次入队
count = 0
while len(queue) > 1:
person = queue.pop(0) # 队首出列报数
count = count + 1
if count == k:
print(person, "号出局") # 报到 k：出局，重新从 1 报数
count = 0
else:
queue.append(person) # 没报到 k：排到队尾
print("最后留下：", queue[0], "号")2 号出局 4 号出局 1 号出局 5 号出局 最后留下： 3 号
假设输入为「5 2」：出局顺序 2、4、1、5，最后留下 3 号。
04 · 逐步理解
每一步只解决一个问题
- 01
第一步：读题，抓住“围成一圈”
题目关键词：围成一圈、依次报数、报到 k 出局、从下一位重新报数。圆圈没有队尾，出列的人回到队伍末尾——这正是在暗示我们用队列：队首出列，没出局就 append 回队尾，队列自己就转成了圈。
- 02
第二步：先手动模拟小样例
n=5、k=2：队列为 [1,2,3,4,5]。1 报 1 回队尾，2 报 2 出局；3 报 1 回队尾，4 出局；5 报 1、1 报 2 出局；3 报 1、5 出局——最后剩 3。纸上模拟一遍，程序的每一步就都有了对照。
- 03
第三步：写出模拟骨架
while len(queue) > 1 是停止条件：只剩一人时游戏结束。每轮 pop(0) 请队首出列报数，报数器 count 加 1；报到 k 就出局并把 count 归零，否则 append 回队尾。
while len(queue) > 1: person = queue.pop(0) count = count + 1 - 04
第四步：出局的两个动作别漏
出局要做两件事：不把他放回队列，并且 count 归零重新报数。漏掉 count = 0 是最常见的错误——下一位会从 k+1 接着数，整个出局顺序全乱。
if count == k: count = 0 else: queue.append(person) - 05
验证：小样例 + 特殊边界
先跑 5 2 看是否留下 3 号；再试 n=1、k=1 的极端情况：队列里只有一人，while 直接不进入，输出 1 号，正确！边界想全，隐藏测试点才拦不住你。
- 06
这道题的后台
它就是大名鼎鼎的“约瑟夫问题”。n 最大 1000，纯模拟完全够用；以后数学会教你公式法，但考场上队列模拟是最稳的拿分姿势。去题库“击鼓传花”独立 AC 一遍！
05 · 练习与检验
自己写出来，才算真正学会
- 1用手边的 5 张纸条手动模拟一遍
- 2运行程序，输入 5 2 看出局顺序
- 3对照纸条验证每一步出队、入队
- 4改成输入 6 3，预测答案再验证
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
工程能力异常、文件、测试与调试读懂报错、缩小问题、设计测试，并安全地打开、读取和关闭文本文件。＋
正式定义
异常是在运行期间表示错误或特殊情况的对象。调试是用可复现输入和证据定位实际行为与预期行为差异的过程；文件对象连接程序与持久化字节数据。
必须掌握
- 先读 traceback 最后一行的异常类型与消息，再从最靠近自己代码的栈帧向上追踪。
- try 只包可能失败的最小代码；except 捕获具体异常；else 处理成功路径；finally 做必需清理。
- raise 主动报告不满足的前置条件；assert 用于开发期内部假设，不用于校验不可信用户输入。
- with open(...) as file 会在退出代码块时可靠关闭文件。文本模式必须明确编码，本站统一推荐 encoding='utf-8'。
- 测试至少包含正常值、边界值、空数据、极端值和反例；每个测试只应有明确目的。
- 定位错误时一次只改一个假设，保留能稳定复现问题的最小输入。
OPEN MODES
文件打开模式速查
基本动作 r/w/x/a 与文本或二进制 t/b、更新标记 + 组合使用，例如 rb、w+。文本文件建议明确 encoding='utf-8'。
| 标记 | 作用 |
|---|---|
r | 读取；文件必须存在 |
w | 写入；先清空已有文件，不存在则创建 |
x | 独占创建；已存在则报错 |
a | 追加；写入位置在文件末尾 |
t | 文本模式（默认） |
b | 二进制模式，读写 bytes |
+ | 更新模式，同时允许读写；与 r/w/x/a 组合 |
常见误区
- 使用 except: 吞掉所有错误
- 只测题目样例就认为程序正确
- 文本文件不写 encoding
- 修复报错表象却不验证根因
适用边界
- 在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
- 二进制文件、JSON/CSV 和数据库各有专门格式与错误处理方式，不能按普通文本随意拆分。
核心数据结构栈、队列、链表与并查集按访问顺序和更新需求理解线性结构，并掌握各操作的真实代价。＋
正式定义
栈按后进先出访问，队列按先进先出访问，链表用节点引用连接次序，并查集维护元素所属的动态不相交集合。数据结构的价值在于为特定操作提供清晰语义和复杂度保证。
必须掌握
- Python list 的尾部 append/pop 可作栈，均摊 O(1)。
- 队列应使用 collections.deque 的 append/popleft，避免 list.pop(0) 的 O(n) 搬移。
- 循环队列用固定数组、队首队尾下标和取模复用空间，必须约定空与满的判定。
- 单链表节点保存值和 next；已知前驱时插入删除 O(1)，按下标查找仍是 O(n)。
- 并查集的 find 找代表元，union 合并集合；路径压缩与按大小/秩合并使均摊代价近似常数。
- 选择结构前先列出最频繁操作：随机访问、两端操作、按键查找或集合合并。
常见误区
- 用 pop(0) 实现大规模队列
- 空栈空队列仍然弹出
- 链表改指针时丢失后续节点
- 并查集只改父节点却不理解代表元
适用边界
- Python 没有课程必需的内置链表类型，教学实现用于理解指针关系；工程中应根据实际操作选择成熟容器。
- 并查集擅长连通性合并，不支持高效删除或一般最短路。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
完成检查