猴子选大王：用队列优雅破解约瑟夫环（PTA实战）

PTA上数据结构实验里十个学生里有八个会被“猴子选大王”这道队列算法设计题绊一下。有人卡在题意理解上有人卡在下标循环上还有人明明在本地跑出了正确结果提交到PTA却总有一两个测试点过不去。这道题说白了就是经典的约瑟夫环n只猴子围成一圈从编号1开始报数报到固定数字m的猴子退出圈子接着从下一只猴子重新从1报数直到最后剩下一只当选猴王。用队列来解恰好是把“围成一圈”这个过程直接翻译成出队、入队操作。你不需要维护复杂的循环下标只需要记住一条规则没被淘汰的猴子从队头挪到队尾被淘汰的猴子直接出队。这篇文章从题目拆解、队列原理、代码实现一直讲到PTA调试踩坑按实际做题的顺序捋一遍适合正在做数据结构实验的新手也适合想把约瑟夫环彻底吃透的备赛选手。1. 题目到底在考什么先别急着写代码1.1 完整题干与隐藏考点PTA和很多教材实验册里的题干都长这样“一群猴子要选猴王。让N只候选猴子围成一圈从某位置起顺序编号为1~N号。从第1号开始报数每轮从1报到m凡报到m的猴子即退出圈子接着又从紧邻的下一只猴子开始同样的报数。如此不断循环最后剩下的一只猴子就选为猴王。请问最后当选的是几号”有些版本只给一个输入n因为报数值固定为3标题里的“3”多半就是这么来的有些版本会给两个输入n和m。不管哪种包装核心逻辑完全一致。读题时最容易踩的坑是只盯着“淘汰”这两个字却忽略了“围成一圈”和“下一只重新报数”这两条关键约束。很多同学第一反应是拿数组存编号淘汰一个就把它标记为0然后每次从头到尾扫描找下一个“活着”的猴子。这个思路本身没错但代码写起来特别容易乱当前报数的人到底在哪个下标下一轮从哪里开始如果m很大每次都要绕好几圈扫描次数爆炸。实际做题时这类方案不是超时就是答案错误因为逻辑分支太多任何一个边界没处理干净就全盘错。这道题真正想考的是你对队列的理解程度尤其是“队尾接队头”的环形特性。约瑟夫环的英文叫Josephus problem本质上是一个循环淘汰问题。你可以把圈子想象成一条首尾相接的队伍队首的人永远是最先报数的那个。报数没有报到m的人相当于绕了一圈又回到了队伍末尾报到m的人直接离开队伍。这么一翻译整个题目就变成了两个队列操作一个是“出队再入队”一个是“出队”。数据结构实验课把这题放在队列章节后面意图非常明显——让你用队列来模拟过程而不是用数组硬算。另外还要注意输出要求。有些版本只输出最后猴王的编号有些版本要求按淘汰顺序输出编号还有些版本要求空格分隔、末尾不能有多余空格。这属于题面细节我在第4部分会专门讲。做题第一步不是写代码而是把输入格式、输出格式、数据范围这三件事看清楚否则白写半天。1.2 为什么队列是这道题的最优数据结构我见过不少人的第一反应是用数组理由是“反正n也不大直接模拟循环不就行了”。数组确实能做但你得自己维护一个逻辑环通常要用一个变量记录当前轮到谁再用另一个计数器扫描活着的元素。问题是删除一个元素之后数组里的空位怎么处理如果用标记法删除只是打个记号每次都要越过已经淘汰的猴子如果用前移法删除后要把后面的元素全部往前搬。这两种做法都不是不行但代码的复杂度和出错率都比队列高一个量级。链表也可以做而且循环链表和人围成一圈的模型非常贴合。可链表代码量偏大要写结点结构体、初始化、删除结点、释放内存实验课如果前面还没把指针吃透额外引入的内存管理问题会喧宾夺主。我在实际辅导时见过一个学生用循环链表写结果delete函数里忘了处理尾指针程序一跑就段错误查了半个小时才发现是链表在只有一个结点时把自己搞丢了。这类问题不是不能解决而是没必要在这道题里给你们增加负担。队列方案最优雅的地方在于它把“环”这个概念直接内置了。用循环队列队尾天然连接队头用链式队列每个结点用完就释放循环逻辑同样顺畅。你只需要想清楚一件事队头的人正在报数。报数没到期出队再入队这个人绕到队尾报数到期直接出队。整个过程和题目的文字描述几乎一一对应写起来顺手检查起来也方便。我在后面会用一个5只猴子的例子完整演算一遍看完你就知道为什么队列方案是这道题的主流做法。这里顺带提一句扩展视野队列这套先进先出的思想后面会在消息队列、阻塞队列、线程池乃至嵌入式里的相关队列组件中以各种变体出现本质都是同一个道理。现在把基础队列玩明白收益远不止这一道题。2. 队列模拟的核心逻辑把报数翻译成出队入队2.1 手工模拟一遍5只猴子报到3概念讲再多不如动手走一遍。假设n5m3初始队列从队头到队尾依次是1、2、3、4、5。注意队头就是当前报数的人。第一轮开始队头是1报数1。1没有报到3所以把1从队头拿出来放到队尾。队列变成2、3、4、5、1。接着队头变成2报数2。2也没有报到3同样出队再入队队列变成3、4、5、1、2。现在队头是3报数3正好报到m3被淘汰直接出队不再回队尾。此时队列变成4、5、1、2下一轮从4开始报数完全符合题意。第二轮接着走。队头4报数1没被淘汰挪到队尾队列变成5、1、2、4。队头5报数2没被淘汰挪到队尾队列变成1、2、4、5。队头1报数3被淘汰队列变成2、4、5。这一轮淘汰了1。第三轮2报数1挪到队尾队列变4、5、2。4报数2挪到队尾队列变5、2、4。5报数3被淘汰队列变成2、4。第四轮2报数1挪到队尾队列变4、2。4报数2挪到队尾队列变2、4。2报数3被淘汰队列只剩4。最终猴王是4。这个手工模拟结果很重要建议你记下来n5、m3时淘汰顺序是3、1、5、2最后剩下4。后面调试程序时拿这组数据一跑如果输出对不上马上能知道是哪里出了问题。为什么这个流程能精确模拟“围成一圈”因为“出队再入队”本质上就是让当前报数者走到队伍末尾相当于在圆圈里绕到下一只猴子的后面。所有没被淘汰的猴子都在不断轮转只有报到m的猴子会被真的移出队伍。这个过程里你不必关心猴子在圆圈里的绝对位置队头永远代表“下一个该报数的人”这个不变量一旦建立代码就不会乱。2.2 循环队列与链式队列怎么选实现队列有两种常见方案数组循环队列和链式队列。猴子选大王这道题我推荐数组循环队列但链式队列的逻辑也必须能看懂因为不同学校的实验要求可能强制指定。数组循环队列用两个下标一个叫front指向队头一个叫rear指向队尾元素的下一个位置。入队操作是q[rear] x; rear (rear 1) % MAXN;出队操作是x q[front]; front (front 1) % MAXN;。判空条件是front rear判满条件是(rear 1) % MAXN front。这里的取模操作就是在实现“队尾接队头”的环形结构很多人第一次看到%都懵其实你就把它想成钟表走到12点后重新从1开始道理一模一样。循环队列有一个经典天坑判满必须留一个空位。也就是说一个大小MAXN的数组实际最多只能存MAXN-1个元素。如果你把数组开成恰好n大小队列全满时判断条件会认为它还有空位继续入队就会覆盖数据反之如果你用其他方式判断容量又可能提前认为队列满了。稳妥做法是MAXN至少等于n1通常开100005这种安全值就够了。链式队列则是用单链表实现队头指针front指向第一个结点队尾指针rear指向最后一个结点。入队在队尾追加新结点出队在队头删除结点。链式的好处是不用担心容量问题也不需要用取模操作模拟环形坏处是每个结点都要malloc如果老师要求你释放内存写完还得逐个free代码量会明显增加。如果你已经掌握链表用链式队列完全没问题主循环的逻辑和数组版本一模一样只需要把push和pop替换成链式操作函数就行。关于“选哪个”我的建议很简单如果题目没有强制要求链式队列直接用循环队列。因为这道题考察的算法设计重点是约瑟夫环的模拟过程不是内存管理。把指针、分配、释放这些细节混进来很容易让学生分心也会增加调试成本。链式队列更适合在专门的链表练习里用那边才是它的主场。3. 完整代码实现与关键行逐段拆解3.1 可直接提交的C语言代码下面这段代码是数组循环队列版本逻辑清晰可以直接提交到PTA。先看完整代码再逐段解释。#include stdio.h #define MAXN 100005 int q[MAXN]; int main() { int n, m; scanf(%d %d, n, m); int head 0, tail 0, cnt 0; for (int i 1; i n; i) { q[tail] i; tail (tail 1) % MAXN; cnt; } while (cnt 1) { for (int i 1; i m; i) { q[tail] q[head]; head (head 1) % MAXN; tail (tail 1) % MAXN; } head (head 1) % MAXN; cnt--; } printf(%d\n, q[head]); return 0; }如果题目固定报到3只输入一个n那就把scanf(%d %d, n, m);改成scanf(%d, n); m 3;其他不用动。这段代码的核心是head、tail、cnt三个变量head指向队头tail指向队尾下一个空位cnt记录当前队列里的猴子数量。用cnt而不是直接判断head tail是因为循环队列里判空和判满都靠这两个下标的相对位置但我们已经知道实际有多少只猴子没必要绕弯直接看cnt更直观。初始化阶段从1到n依次入队。注意入队前先赋值给q[tail]再让tail后移这是队列的标准写法。cnt同步加1保证队列的实时长度。while循环的条件是cnt 1意思是只要还剩至少两只猴子就要继续报数淘汰。循环内部先做一个for循环把前m-1个猴子“出队再入队”然后让head再后移一位相当于把报到m的猴子直接淘汰。最后cnt--队列人数减少跳出循环后队头元素就是唯一剩下的猴王。这段代码的时间复杂度是O(n*m)空间复杂度O(n)。对常见实验数据绰绰有余。如果你提交后提示运行超时等一下我会讲数学公式解法那才是大范围数据的正解。3.2 最容易写错的三个位置第一个高频错误是while循环的结束条件。有些同学写while (head ! tail)这是循环队列的判空条件。问题是当队列只剩一个元素时head ! tail依然成立程序还会进入循环把这个最后的猴子也淘汰掉。等到队列真的空了再想去访问队头元素q[head]就是垃圾值或者越界。正确思路是只要队里还有多于一只猴子就要继续淘汰所以条件写成cnt 1如果你用size变量更方便。用判空条件当结束条件是这道题错误率最高的写法之一。第二个高频错误是内层for循环的范围。报数从1开始报到m前m-1只猴子都不淘汰都要出队再入队所以for (int i 1; i m; i)循环体执行m-1次。如果写成i m就会多轮转一次把本来该在第m个位置淘汰的猴子提前挪走了淘汰对象整体错位。如果写成i 0同样会多跑一次。我在改作业时经常看到这种边界差1的错误测试样例小的可能碰巧蒙对数据一换就露馅。第三个高频错误是忘记取模。head (head 1) % MAXN;和tail (tail 1) % MAXN;这两行里的% MAXN不能省。有人觉得“我数组开得足够大越界也没事”这种侥幸心理很容易在凑巧的大数据下翻车。一旦下标跑到MAXN外面轻则读到脏数据重则直接段错误。PTA的段错误提示就俩字Runtime Error但原因可能是数组越界也可能是循环死循环导致无限增长排查起来非常折磨。所以每次都规范地取模是省时间的明智选择。顺带说一个不太起眼但也很容易错的点数组大小。前面提到循环队列判满要留一个空位所以MAXN必须大于n。如果你的数据范围是n≤100000MAXN100005够用因为队列元素最多100000个还留了一个多余位置。千万别开成MAXN100000否则恰好满队列时逻辑会出问题。3.3 数学公式解法能帮你验算和救急约瑟夫环有名是因为它除了模拟之外还有一个漂亮的数学递推。我不建议一上来就背公式但学会它可以用来验证队列程序跑得对不对也是算法设计能力的一种体现。这个递推要反着看假设现在只有1个人那幸存者一定是0号这里用0表示相对偏移方便取模。然后逆推回去每次往圈子中加入一个人新的幸存者位置等于(上一个幸存者位置 m) % 当前人数。写成代码就是int s 0; for (int i 2; i n; i) { s (s m) % i; } printf(%d\n, s 1);为什么从i2开始因为一开始只有1个人时幸存者相对位置是0之后每增加一个人就要按新的总人数重新计算一次位置。最终结果是s 1因为前面用的是0到n-1的编号题目要求1到n的编号。拿n5、m3验证i2时s(03)%21i3时s(13)%31i4时s(13)%40i5时s(03)%53最后输出s14和手工模拟完全一致。这个解法的时间复杂度是O(n)空间复杂度O(1)比队列模拟快得多。如果PTA的测试数据把m设得特别大比如m等于100000队列模拟每轮都要转m-1次哪怕n只有100也可能超时。这时候数学公式就是救命稻草。但题目如果明确要求用队列完成实验你还是要写队列版本公式只能在调试时当验证工具。我的建议是先写队列模拟跑通后用公式解法交叉验证结果两个版本都理解了才算真正拿下这道题。4. PTA提交实战常见错误与调试经验4.1 常见报错类型速查表在PTA上做题报错信息就那几类但原因常常千奇百怪。我把这道题最常见的报错和原因整理成了一张表方便你对照排查。报错类型常见原因解决办法Compile Error语法错误、用了不规范的写法检查分号、大括号变量定义放函数开头Wrong Answer报数边界错、输出格式错、输入读取错重点检查for循环的im还是imscanf是否匹配输入格式Runtime Error数组越界、除零、访问空指针检查是否忘了取模MAXN是否开小循环是否死循环Time Limit Exceededm太大导致轮转次数过多改用数学公式解法或检查是否写了死循环Presentation Error输出格式和题目不完全一致检查空格、换行、末尾不能有多余空格其中Presentation Error在PTA里很特殊它不直接算错误但也不会通过。常见触发方式是每个编号后面都跟了一个空格而题目要求末尾无多余空格。这种错最憋屈明明答案数字全对却因为空格多了被卡。我的习惯是输出前先想清楚这一行最后一个字符到底应该是数字还是换行尽量避免边输出边拼字符串的写法容易出问题。有一个很隐蔽的输入坑有些PTA老题的输入是n,m中间有逗号而有些是n m中间是空格。如果你用scanf(%d %d, n, m)去读带逗号的输入第二个数就读不进去m会变成未初始化的随机值答案自然是错的。做题前必须先看输入格式说明或者直接看题目样例输入是不是有逗号。如果样例是5,3你就写scanf(%d,%d, n, m);把逗号原样写进去。4.2 用打点输出定位逻辑错误程序过了编译但是答案错误这时候最有效的调试方式是在关键位置加打印语句把队列的实时状态打出来。比如在主循环里加这样一段printf(debug: 当前队列为 ); for (int i 0; i cnt; i) { printf(%d , q[(head i) % MAXN]); } printf(\n);每次轮转前打一次当前队列你就能看到每轮开始和结束时队列的变化。拿n5、m3跑一遍如果打印出来的队列变化和你手工模拟的不一致那就非常容易定位问题是少轮转了一次还是多淘汰了一个。这个方法对新手特别友好因为你会亲眼看到“1出队再入队之后跑到队尾”这个动作发生现场而不是在脑子里猜。我自己调试这道题时习惯把手工模拟写在纸上程序每打一行就和纸上对一行。第一次写队列程序的同学最大的问题往往不是不会调用函数而是不确定“前m-1只猴子挪到队尾”和“第m只猴子直接出队”这两步到底谁先谁后。逻辑顺序想反了打印出来的队列就会从第一次淘汰就错。要提醒一句调试用的printf在最终提交前一定记得删掉或者用注释包起来。PTA会把标准输出原样比对多任何一个字符都会导致答案错误。我见过有学生本地跑得好好的提交上去全是Wrong Answer最后发现是debug输出没删干净。这个坑踩一次能记住很久。4.3 输入输出格式与数据边界的坑关于多组数据。如果题目要求处理多组输入直到EOF写法是while (scanf(%d %d, n, m) ! EOF)但要注意每组数据都要重置head0; tail0; cnt0;。很多同学忘了重置第一组跑完第二组的队列里残留了第一组的数据结果一组错带动后面全错。PTA大部分题是一次输入一组但保险起见做题前先看清题目是否写了“多组数据”。关于边界值。最容易被忽视的是n1。一只猴子当选猴王根本不需要报数直接输出1。上面的代码里初始化后cnt1while循环条件不成立直接输出q[head]也就是1逻辑天然正确。如果你把循环结束条件写错n1时反而会把这只唯一的猴子淘汰掉输出结果变成垃圾值。第二个边界是m1。报到1就淘汰意味着每轮队头直接出局最终剩下最后一只也就是编号n。代码里内层for循环一次都不执行head直接后移淘汰队头最终留下的确实是最后一个元素和正确逻辑一致所以m1也能处理。还有一个数据范围的坑如果题目给的n很大比如十万而你的MAXN只开了1005那数组越界几乎是必然的。遇到段错误第一个要怀疑的就是数组容量。不要凭感觉开数组去题面找数据范围一般会写“n≤100000”那你就开100005留点余量永远是对的。关于输出编号的细节。如果题目要求输出淘汰顺序那么你需要把每次被淘汰的编号按顺序存下来最后一起输出不要一边淘汰一边printf否则无法控制空格格式。如果只要求输出最后猴王那就简单了循环结束后打印队头即可。我再次强调写代码前先花30秒把题目的输入输出格式读三遍这30秒能帮你省下半小时的返工时间。最后再分享一个小经验PTA的经典版本里答案输出要求printf(%d\n, ans);不要加多余的提示语。有些同学喜欢在本地调试时打印“result is:”提交前又没删结果所有测试点全挂。写PTA题可以养成一个习惯主函数的输出语句永远只输出题面要求的内容调试信息走临时printf提交前全局搜索一下“debug”或“printf”检查干净。这道题我前前后后带过不少学弟学妹做个人最深的体会是很多人不是不会写队列而是没有把“报数”和“出队入队”这两件事真正对应起来。一旦你脑子里有“队头就是当前报数者”这幅图整道题的代码就是顺水推舟。最后分享一个小技巧无论题目要求输出什么我都先准备一份n5、m3的手工模拟结果放在旁边程序跑完对一遍3、1、5、2的淘汰顺序只要差一个数立刻就能定位是边界写错还是循环顺序写错。这道题作为队列入门的第一个模拟题性价比是真的高。