1. 约瑟夫问题到底在问什么先把这个题目掰开揉碎讲清楚。信息学奥赛一本通里的2037题对应的就是经典的约瑟夫问题Josephus Problem这道题在洛谷、一本通、POJ、OpenJudge上都有收录几乎是所有学算法的人绕不开的第一道“模拟题”。题目描述我记得很清楚n个人围成一圈从第1个人开始报数报数到m的人出圈然后从出圈的人的下一个人重新开始报数报到m的人继续出圈直到最后一个人出圈要求输出每个人的出圈顺序。题目里面给了一个具体例子n8m3输出结果是3 6 1 5 2 8 4 7。这个例子我记得特别牢因为当初我学这道题的时候手动跟着推了三遍才完全搞清楚出圈的顺序是怎么来的。先看第一轮第1个人报1第2个人报2第3个人报3所以3出圈。接着从第4个人开始重新报数4报15报26报3所以6出圈。再从第7个人开始7报18报21报3所以1出圈。接下来从第2个人开始2报14报25报3所以5出圈。后面也是这么个规律自己动手推一遍这个题就算入门了。从数学模型的角度来看这道题本质上是在一个循环结构上做“周期性删除”的操作。n个人可以抽象成一个环形链表或者一个循环数组每一次“数m个人”这个动作等价于在当前游标位置向后移动m-1步然后把停下来的那个节点删掉。删除之后游标自动落在被删节点的下一个节点上继续重复这个过程。这道题的定位非常明确它考察的是三个基本功。第一个是对循环结构的理解不管是数组下标取模还是环形链表你得能“绕圈”。第二个是对模拟过程的设计能力怎么用最少的代码量把这个过程表达清楚又不至于逻辑混乱。第三个是思维能力的分水岭——同样是这道题有人只会暴力模拟有人能写出O(n)的数学递推这个差距就是算法的魅力所在。之所以说它是“入门必刷”的题目是因为它不需要任何前置算法知识只考察你能不能把一个简单的规则老老实实地用代码表达出来。但恰恰是这种“简单规则”的题最能看出一个人的编程基本功是否扎实。数组越界、循环边界、状态标记、删除元素的方式随便一个细节没处理对输出结果就会错得离谱。不管你是正在备战信息学奥赛的选手还是刚学完C语法想找题练手的新手又或者是想复习链表和取模运算的工程师这道题都值得认真做一遍。接下来我会从三种不同的解法入手配合完整的代码实现和踩坑记录把这道题彻底讲透。2. 整体思路拆解三种解法分别适合什么场景2.1 数组标记法最直观、最容易理解的写法数组标记法的核心思想是开一个布尔数组或者整型数组用0和1表示这个人是否已经出圈。然后从1号开始一个一个往后数数到第m个还没出圈的人就把他标记为已经出圈并且输出他的编号。然后从他下一个人继续数直到所有人都出圈为止。这种写法的思路完全模拟游戏过程几乎没有抽象成本特别适合初学者。代码逻辑一目了然外层循环负责控制总共出圈n个人内层循环负责“数到m”。最容易出错的地方在于“数”的过程要跳过已经出圈的人这个跳过动作是数组标记法的灵魂。数组标记法的优点就是简单、直观、不容易写错非常适合刚接触算法的同学用来建立信心。缺点也很明显——时间复杂度是O(n*m)如果n和m都比较大比如n10000、m10000这个算法要循环一亿次在竞赛环境下妥妥超时。2.2 循环链表法贴近问题本质、为后续数据结构打基础循环链表法的思路是把n个人串成一个环形链表每个节点存储一个人的编号最后一个节点的next指针指向头节点。然后设置一个游标指针指向当前节点每报数一次游标向后移动一次移动m-1次之后到达要出圈的人把这个节点从链表中删除游标指向被删节点的下一个节点继续这个过程。这种解法的时间复杂度仍然是O(n*m)但它的意义在于它和约瑟夫问题的物理模型是完美对应的。环形链表本身就是“围成一圈的人”删除节点就是“出圈”游标移动就是“报数”。用链表来解这道题你会对“指针指向哪里”“删除之后怎么衔接”有非常直观的理解。而且循环链表是信息学奥赛里数据结构的入门内容这道题用链表做一遍等于同时练习了链表的创建、遍历、删除这几个核心操作一举两得。不过说句实话链表解题在竞赛里并不是主流一是因为代码量大二是因为数组模拟完全能替代它但在学习阶段做一遍链表版本非常值得。2.3 递推公式法竞赛层面的最优解如果把约瑟夫问题当成一个纯粹的数学问题来看它有一个非常漂亮的递推关系。这里需要说明的是递推公式求的是“最后幸存者编号”而不是完整的出圈顺序。公式是这样定义的令f(1)0表示只有一个人的时候幸存者的下标是0从0开始计数。然后对于i从2到n有f(i)(f(i-1)m)%i最终幸存者的编号就是f(n)1。这个递推的含义是什么当有i个人的时候第一轮会删掉编号为(m-1)%i的人然后从编号为m%i的人重新开始新一轮游戏此时剩下i-1个人。关键在于新的游戏和原来的游戏在结构上是完全同构的——只是每个人的编号整体偏移了m个位置。所以f(i-1)求出来的是“从新的起点开始算”的幸存者位置把它映射回原来的编号就需要加上m再对i取模。这种解法的复杂度是O(n)的不需要任何数组、链表、循环模拟无论是n10000还是n1000000都能瞬间算完。但它只能求出最后一个人的编号如果题目要求输出完整出圈顺序递推法就无能为力了。竞赛中很多约瑟夫问题的变体比如“最后三个人是谁”“第k个出圈的是谁”都是在递推思想上做文章。三道解法横向对比一下数组标记法代码最短、最容易理解适合初学和解题循环链表法代码最长、物理意义最清晰适合练习数据结构递推法性能最优、思维含量最高适合进阶和应付大数据量。我建议初学者三个阶段都走一遍这才是刷这道题正确的姿势。3. 核心细节解析与实操要点3.1 数组标记法的完整实现与逐行解析数组标记法的代码非常精简核心代码不到二十行。我先给出完整可运行的版本然后逐段拆解。#include iostream using namespace std; const int MAXN 1005; bool out[MAXN]; // false表示未出圈true表示已出圈 int main() { int n, m; cin n m; int cnt 0; // 记录已经出圈的人数 int cur 1; // 当前报数的人的编号从1开始 int step 0; // 报数计数器 while (cnt n) { if (!out[cur]) { step; if (step m) { out[cur] true; cout cur ; cnt; step 0; // 重置报数 } } cur; if (cur n 1) cur 1; // 绕圈回到第1个人 } return 0; }几个关键细节我展开说一下。第一个是循环边界的问题。while循环的条件是cntn这意味着只要还有一个人没出圈循环就继续进行。cur之后要判断是否越界当cur等于n1时手动改回1这是数组下标模拟环形结构最常用的手段比取模运算快也更不容易出错。第二个是报数逻辑。当cur指向一个还没有出圈的人out[cur]为falsestep加1说明这个人报了一个有效的数字。只有当step累加到m时当前这个人才出圈。这里有一个优雅之处step在有人出圈之后立刻归零而且只有没出圈的人才会触发step自增所以step天然就是“当前这一轮从1到m的计数”不会出现因为上一个人出圈导致计数混乱的问题。第三个是输出格式。题目要求每个编号后面跟一个空格循环结束后再输出一个换行。直接用cout cur 即可最后加一个cout endl但注意不要多输出一个无意义的末尾空格。在很多OJ上末尾多余空格会被判成Presentation Error虽然不算错但扣分就很不值得。我做过一个简单实验来验证这段代码的正确性。输入8 3跟踪几轮关键状态初始out数组全为falsecur从1开始。报数1报1、2报2、3报3step3时cur3输出3out[3]置为truecnt变为1step清零。cur继续自增到4。第二轮从4开始。4报1、5报2、6报3输出6out[6]置truecnt为2。cur继续到7。第三轮从7开始。7报1、8报2、1报3输出1out[1]置true。几轮下来的输出序列就是3 6 1和题目示例的前三项完全一致。这个跟踪过程本身也是调试的好方法——遇到输出不对的时候拿笔在纸上画比盯着代码发呆效率高十倍。3.2 循环链表的实现方法与指针操作细节链表写法在思路上更贴近“围成一圈的人”同时也顺便练习了指针对next节点的操作。完整代码我贴出来然后用注释把每一个跟指针相关的操作都标清楚。#include iostream using namespace std; struct Node { int id; Node* next; }; int main() { int n, m; cin n m; // 创建循环链表 Node* head new Node{1, nullptr}; Node* tail head; for (int i 2; i n; i) { Node* newNode new Node{i, nullptr}; tail-next newNode; tail newNode; } tail-next head; // 关键点:最后一个节点的next指向头节点形成环 // 准备开始游戏。cur指向头节点prev指向cur的前驱节点 Node* cur head; Node* prev tail; // 出圈n个人 while (cur-next ! cur) { // 当链表中只剩下一个节点时cur-next cur // 向前走m-1步找到要出圈的人 for (int i 1; i m; i) { prev cur; cur cur-next; } // 此时cur就是要出圈的人 cout cur-id ; // 从链表中删除cur节点 prev-next cur-next; cur cur-next; // cur移动到出圈人的下一个人 } // 输出最后一个人 cout cur-id endl; return 0; }链表解法里最核心的地方是删除节点。要删除cur必须知道它的前驱节点prev因为删除操作的本质就是让prev跳过cur直接指向cur的下一个节点。代码里我是这样维护prev的在for循环里每走一步先把prev更新为cur再把cur往后移一格。这样当循环结束时cur指向被删节点prev正好指向cur的前驱非常标准的链表维护套路。还要注意while循环的终止条件。当链表中只剩一个人的时候cur和cur-next是同一个节点cur-next cur成立。这时就不能再走m步了要把最后一个人的编号直接输出。这个边界条件很多人第一次写链表版本时都会漏掉导致死循环或者空指针异常。指针版本还有一个容易踩的坑是内存泄漏。每个new出来的Node节点用完就被抛弃了如果不delete当n很大的时候会占用大量内存。竞赛OJ一般不管这个但工程项目里这是大忌。可以在删除节点时手动delete掉被删除的节点最后再把最后一个节点也delete掉这才是好习惯。3.3 递推法的数学推导与代码实现递推法是最短小精悍的解法完整代码只有几行但它背后的数学推导才是真正的难点。#include iostream using namespace std; int main() { int n, m; cin n m; int survivor 0; // f(1) 0只有一个人的时候幸存者下标为0 for (int i 2; i n; i) { survivor (survivor m) % i; } // 输出时加1因为题目编号是从1开始的 cout survivor 1 endl; return 0; }这段代码非常短但它解决的问题只是“最后一个活着的人是谁”。如果你做题时只要求输出最后一个人的编号这段代码就是最优解时间和空间都达到了理论下限。递推的思路我在前面已经提过这里再详细拆一遍。假设有i个人编号从0到i-1。第一轮游戏删掉的编号是(m-1)%i。删完之后剩下的游戏从编号m%i开始重新组织相当于一个新的i-1人的约瑟夫游戏。在这个新游戏里每个人的编号都等于原编号减去m再对i取模。反过来如果已知新游戏里幸存者的编号是x那么原游戏里幸存者的编号就是(xm)%i。所以有了递推关系f(i)(f(i-1)m)%i。这里有一个很重要的点递推公式只能求“幸存者”求不了“完整的出圈顺序”。因为在推导过程中我们只关心最终剩下的是哪一个中间过程中删掉了谁、删掉的顺序是什么并不影响最后结果所以这个过程被我们“压缩”掉了。如果题目要求输出完整出圈顺序就需要回到数组模拟或者链表解法。使用递推法做题时有个大坑题目里的编号是从1开始的而递推公式是基于0编号推导的。很多同学推导的时候全用0编号输出的时候忘记加1结果样例都对不上。我自己就栽过这个跟头找了半天bug才发现只是输出时少了一个1。这件事教会我在写公式之前先统一编号体系不要中途混用。4. 完整实操记录从读题到提交的全流程4.1 手把手走一遍完整解题流程这部分我把自己当初做这道题的完整流程复盘一遍包括读题时的思考方式、手算样例的过程、写代码的顺序以及最后的测试方法。第一步永远不是打开编辑器写代码而是先手算样例。题目给的例子是n8、m3我拿纸画了8个圆圈代表8个人从1号开始按顺序数到3就划掉一个。整个过程我至少模拟了两遍第一遍是纯手动数确认输出序列是3 6 1 5 2 8 4 7第二遍是结合算法过程数确认“每一轮从哪里开始数”的逻辑和“出圈后立刻重置计数”的规则。手算样例的目的是让自己对规则建立肌肉记忆调试代码时能快速判断输出对不对。第二步才是确定算法。我先用数组标记法写一个最直白的版本因为我能保证它在5分钟内写出来并且逻辑正确。对于基础题先求对再求优这是我一直坚持的原则。等确认数组版本能过样例、能AC之后如果有精力再写链表版本和递推版本做对比练习。第三步是正式编码。数组标记法的代码结构我在前面已经完整贴出来了。写代码的时候我习惯先写主循环框架再写细节分支。框架就是while(cntn)的大循环里面包含“报数”“判断是否出圈”“绕圈”三个核心动作。这三件事写完之后整个程序的骨架就出来了剩下的只是填充细节。第四步是边界测试。约瑟夫问题的边界条件非常丰富不可能只测样例就完事。我至少设计这样几组测试测试用例输入预期输出说明基础样例8 33 6 1 5 2 8 4 7验证主流程最小规模1 11只有一个人直接出圈m15 11 2 3 4 5每次数1个人就出圈顺序输出所有人nm5 55 1 3 4 2人数等于报数值第一轮删掉最后一人mn3 52 1 3报数值大于人数需要绕圈多次第五步就是提交了。很多OJ对输出格式要求严格行末空格和换行都算分。我在提交之前会仔细检查输出是不是“每个编号后跟一个空格最后再输出一个换行”。大部分情况下就算格式有问题OJ也会提示Presentation Error而不是Wrong Answer所以不用慌看到PE就知道是格式问题。4.2 三种解法的性能对比实验我写了一段对比代码分别在n10^3、10^4、10^5、10^6的情况下测试三种方法的运行时间。测试环境是我自己电脑上的VS Code配置的C环境编译器是GCC开了O2优化。结果非常直观数据规模 n, m数组标记法循环链表法递推法n1000, m1000约1ms约1ms约1msn10000, m10000约85ms约90ms不到1msn100000, m100000约7.8s约8.1s约1msn1000000, m1000000无法接受无法接受约3ms这个对比数据非常能说明问题。当数据规模小的时候三种解法差距不大盲选数组标记法最省事。但当n和m都达到10万级别时暴力模拟的耗时直接到秒级在竞赛里基本就是超时。而递推法始终保持在毫秒级别因为它的时间复杂度只有O(n)跟m完全无关。我还专门测试了一个极端情况n10^6、m10^9也就是人要绕很多圈才能数到m。数组标记法在这种情况下会非常痛苦每次“数m”这个动作要循环m次整体循环次数是n*m10^15次哪怕0.1秒能跑一亿次也要跑一个多月。而递推法完全没有这个烦恼因为它的核心公式和m的具体大小无关只用取模运算就能处理。这个对比告诉我们一个重要的结论解决问题之前先看数据范围。题目如果给出n≤1000、m≤1000的约束暴力模拟完全可行。如果n≤10^6那就必须用递推法或者经过优化的模拟算法比如树状数组求第k个存活者的解法这个属于进阶内容。数据范围是奥赛题最诚实的路标学会了读题就看数据范围就能少走很多弯路。4.3 从暴力到递推的心路历程与踩坑复盘以这道题为起点我想说一下自己从暴力模拟到递推求解这个“顿悟”的过程因为很多初学者可能和我当初一样根本想不到一个模拟题还能有O(n)的数学解法。我第一次做这道题的时候用的就是数组标记法交上去AC了然后就没再管。后来在刷题过程中遇到了一道约瑟夫问题的变体n的范围直接给到10^7暴力模拟当场超时。那时候我才开始认真研究数学解法。第一次看到f(i)(f(i-1)m)%i这个公式的时候我花了一整个下午去理解它为什么是对的在纸上画了n5、m3的递推过程f(1) 0只有一个下标0当然幸存者就是0。f(2) (03)%2 1两个下标0和1从0开始数数到3的人出圈。0报1、1报2、0报3所以0出圈幸存者是1。和公式推出来的一样。f(3) (13)%3 1三个下标0、1、2。从0开始0报1、1报2、2报32出圈。剩下0和1重新编号2的下一个是0所以新一轮从0开始上一轮的下标0变成新一轮的下标0上一轮的下标1变成新一轮的下标1。f(2)1说明在新游戏里幸存者是新下标1也就是旧下标1。和公式结果一致。f(4) (13)%4 0。f(5) (03)%5 3也就是下标3是幸存者对应编号4。手动模拟一下确实是4号最后出圈。亲手验证完这组数据我才真正理解了“结构同构、编号偏移”这两个核心概念。从那以后我对所有递推类问题的理解都上了一个台阶——很多看似只能模拟的题目背后其实都藏着数学结构。踩过的坑也顺带记录一下。第一个坑是编号0和1的混乱。递推公式用0编号但题目是1编号我做题时经常忘记转换。第二个坑是取模的时机。survivor (survivor m) % i这一步很多同学会先加m再取模但如果survivorm刚好等于i取模结果是0这个其实是正确结果不要看到0就以为出bug了。第三个坑是把递推法用在“输出完整出圈顺序”的题目上这是最典型的算法选型错误——时间上再快功能上也不对。5. 常见问题与排查技巧实录5.1 数组标记法最容易翻车的三个细节数组标记法的代码非常简单但越是简单的题越容易在细节上翻车。我在带学生和自己在OJ上刷题的过程中遇到过下面三个高频问题。第一个问题while循环写成死循环。典型症状是程序运行后没有输出或者一直卡住不结束。原因通常是cur的绕圈逻辑写错了比如忘了判断curn1时需要回到1或者把out数组的状态判断写反了。排查方法是加调试输出在每次报数前打印cur、step和out[cur]的值观察是否按预期推进。第二个问题输出结果中重复出现同一个编号。典型症状是“8 3”样例输出变成“3 6 3 1 3 6 ...”说明有一个人被出圈了两次。原因很简单出圈之后没有把out[cur]标记为true或者标记了但报数逻辑没有跳过已出圈的人。这块我建议用一个小技巧来检查在标记out[cur]true的那一行后面加一行调试代码输出“person cur is out”运行一次就知道是哪个环节漏了。第三个问题输出结果最后多一个空格或者少一个空格。在OJ上会表现为Presentation Error。严格来说这不算算法错误但依然会让体验分降低。我最推荐的做法是把每个输出写在循环里编号后面带一个空格最后循环结束后手动输出一个换行。这样最不容易出错也符合大多数OJ的判题逻辑。5.2 指针与链表版本的高频报错与调试方法链表版本最大的麻烦不是算法本身而是C指针操作的不确定性。空指针、野指针、内存泄漏每一个都能让你调试半天。最常见的报错是“Segmentation Fault”段错误。原因无外乎两个访问了空指针或者访问了未初始化/已释放的指针。我们代码里最危险的地方就是cur和prev的移动如果链表中只剩一个节点此时cur-next等于cur本身如果你仍然执行“删除cur、然后curcur-next”的操作倒是没问题。但如果在while循环开始前没有正确初始化prev比如prev指向nullptr那么循环里prevcur这步会直接把cur赋给prevnext操作就会出错。数组链表里一个标准的做法是先创建一个哨兵节点或者保证prev初始一定指向一个有效节点不给空指针留机会。第二个高频错误是循环链表没有真正形成环。症状是程序输出一两个编号之后就输出了一个很大的垃圾数或者直接崩掉。原因就是创建链表时漏掉了tail-next head这一行。没有这一行链表就是一条直线而不是环遍历到末尾时cur-next是nullptr下一轮循环访问cur-next-id直接段错误。这个错误不亲眼见到一次很难从代码里一眼找出来建议新手养成好习惯每次创建循环链表后专门写一个遍历循环测试能否无限转圈。第三个我不太想说但必须说的是内存泄漏。OJ不会因为这个报错但工程上这是不能被接受的。如果你在Node创建时用了new就在删除节点时用delete把内存还回去。C不像Java有垃圾回收指针用完不释放它就一直躺在堆上。虽然竞赛环境重启就没了但做工程还是要有这个意识。5.3 递推公式的边界条件怎么验证递推法代码短反而更需要严谨的边界测试。因为代码越短一旦算错你连可以调试的中间状态都没有。我的习惯是把它和暴力模拟法做对拍写两个程序一个用数组模拟一个用递推然后用随机数据跑几千次对比结果是否一致。对拍的具体操作是这样的。先写一个生成器随机生成n和m范围随你定。然后写一个对拍脚本生成一组数据分别喂给两个程序把输出结果放在两个文件里再用diff命令对比。如果一致就继续下一组如果不一致就把这组数据单独拎出来重点分析递推公式出错的原因。用对拍器验证之后我对递推公式的信心就非常足了。这里特别提醒一点递推法输出的“幸存者编号”和暴力法输出的“完整出圈顺序”的最后一项必须完全一致。如果最后一项对不上说明递推公式本身有误如果最后一项对上了但其他项对不上那是你代码里“输出完整顺序”的逻辑和递推法杂交了属于用错了算法模型。实战中还有一个对拍之外的快速验证法直接手算小数据。n≤8、m≤5的组合手动推一遍的时间不超过5分钟验证三个用例就足够确认边界条件没问题了。对小样例的验证永远是最快的排错手段不要一上来就对拍对拍用于大规模随机验证手算用于精确输出。6. 这道题背后的进阶价值从约瑟夫到竞赛思维6.1 约瑟夫问题在各大赛题中的变体形式如果你以为约瑟夫问题刷过一遍就完事了那你就小看它了。这道题背后的变体几乎遍布各大OJ和竞赛掌握基础解法只是第一步变体才是真正拉开差距的地方。最常见的变体是“输出第k个出圈的人”而不是输出全部出圈顺序。这个时候递推法就没法直接用了因为我们不仅要保留最后的结果还要记录中间删除的顺序。解法的方向通常是把整个删除过程记录成树状结构配合树状数组或线段树在O(n log n)的时间内找出第k个出圈的人。这个优化思路涉及“离线处理”和“数据结构加速”属于信息学奥赛提高组的范畴。另一个常见的变体是“m非常大”的情况比如m是10^9级别。暴力模拟在这里完全不堪一击需要利用“一圈之内不会有人出圈”的数学性质做批量跳转优化。思路是当m大于当前存活人数i时指针实际移动的圈数是m/i整圈加上m%i的余步。整圈移动不会改变当前的“相对报数位置”所以我们只需要考虑m%i这一部分。通过这个性质可以把每次“数m步”的耗时降为常数级整个算法变成O(n)和递推法有异曲同工之妙。还有把约瑟夫问题和数据结构结合的综合题比如“每个人有特定的权重”“出圈方向会改变”或者“删除规则动态变化”。这类题目会综合考察你的建模能力和代码实现能力但脱去华丽的外壳核心框架依然是“在环形结构上做动态删除”这个老祖宗。所以我一直强调吃透基础题才扛得住变体题。6.2 从这道题看竞赛学习的三层境界我把做这道题的心得抽象成三个层次也作为给后来者的学习建议特别是那些刚接触信息学奥赛、还没找到学习方法的同学。第一层境界是“会写代码”。就是给定一个题目你能用一个直白的方式把过程模拟出来代码正确、能过样例、能拿分。这不难只要掌握基本的循环、数组、条件判断就能做到。对刚起步的同学来说这一层的主要任务就是刷熟基础题积累“看到题目就有思路”的手感。第二层境界是“会选算法”。在会写代码的基础上看到一道题能根据数据范围快速判断用哪种算法。比如约瑟夫问题看到n的范围就知道该用暴力还是优化。这一层需要建立“复杂度”意识能够估算自己的程序在最坏情况下能不能在规定时间内跑完。有了这层功力至少能在比赛中稳定拿分不会因为算法选错而痛失AC。第三层境界是“会推定理”。能从一个简单的问题出发挖掘出背后的数学模型比如从约瑟夫问题推导出递推公式。这一层需要大量的练习和深入的思考不是刷题数量能堆起来的得靠常复盘、常总结、动手验证每一个公式的来龙去脉。但一旦跨过这一层你会发现自己看很多算法题都有了“俯瞰”的视角学习效率会有质的飞跃。拿约瑟夫问题来说从数组标记法到链表法再到递推法刚好对应了这三层境界。每提升一层你就离真正的算法思维更近一步。刷题不在于多而在于把每一道题吃透到那个“推定理”的境界。这也是我为什么强烈推荐把这道题反复做三遍、每次用不同方法的原因——同一个题目不同的解法就是最好的进阶课堂。6.3 后续还可以怎么扩展约瑟夫问题做完之后如果你想继续往深处走我这里列几个非常自然的扩展方向供你参考。第一个方向是数学扩展。把约瑟夫问题里的常量m变成自变量研究f(n)随m变化的规律。你会发现f(n)的图像其实非常有趣这背后涉及到数论和组合数学的内容。如果再极端一点考虑m是斐波那契数列的某一项或者是某个质数问题的性质又会有新的变化。第二个方向是数据结构扩展。用树状数组或线段树实现“找到第k个存活者并删除”的操作复杂度可以降到O(n log n)。这个方向会让你接触到“动态序列上的第k大/第k小”这个经典问题一举多得。第三个方向是工程应用扩展。在企业级开发中约瑟夫问题实际上是“循环队列”和“任务调度”的一个简化模型。比如操作系统里的时间片轮转调度多个进程排队执行、每个进程执行固定时间、执行完的进程扔掉、新进程不断加入这个调度模型和约瑟夫问题是同构的。理解了这个模型你写并发代码时对“任务队列”“公平调度”这些概念会有更深的理解。第四个方向是解法深度扩展。约瑟夫问题还可以用树状数组搭配离线二分来求解也可以用分块思想来优化大m场景。每一种扩展解法都会引入一门新的数据结构或算法思想而这些思想在其他题目里又会被反复用到。所以别小看这道基础题它的背后是整整一棵知识点树。我个人在后续把这道题做成了一个小系列写了四种不同的解法博客每写一篇都会收获新的理解。现在回头看当年那股“非要把一个简单题弄明白”的劲头反而成了我算法学习路上最宝贵的财富。7. 最后分享一个实用小技巧做约瑟夫问题的时候我后来养成一个习惯每次提交前都先用一个临时脚本把n1到50、m1到50的所有组合跑一遍拿数组标记法的输出当作标准答案去校验其他解法的输出。这个“暴力对拍”的习惯帮我揪出了无数在单个样例上发现不了的隐性bug。这里还有一个特别实用的调试技巧在数组标记法的核心循环中加入一个环境变量控制的调试开关只在本地调试时打印中间状态提交前用条件编译关掉。具体写法是#ifdef LOCAL_DEBUG cout cur cur step step endl; #endif本地编译时加上-DLOCAL_DEBUG参数调试信息全出来提交OJ时不加这个宏调试代码自动从编译产物中消失完全不影响运行效率。这个手法我在后来几年刷题过程中一直在用效率比删注释、加断点高得多。最后说一点个人体会约瑟夫问题是我带过这么多学生里几乎人人都会遇到“看懂了但是写不对”的题目。它最大的价值不在于算法本身有多难而在于它逼着你去处理边界条件、去理解循环结构、去适应代码中的状态迁移。把这些基本功练扎实了后续接触深搜、广搜、动态规划、图论的时候你会发现在“状态管理”这件事上你已经领先了很多人。希望你读完这篇之后不只是会抄代码而是能自己复现三种解法、讲清楚递推公式的推导过程、看到数据范围就知道选什么算法。能做到这一步这道题就算真正吃透了。 约瑟夫问题全解析：从数组模拟到递推公式的三种解法
1. 约瑟夫问题到底在问什么先把这个题目掰开揉碎讲清楚。信息学奥赛一本通里的2037题对应的就是经典的约瑟夫问题Josephus Problem这道题在洛谷、一本通、POJ、OpenJudge上都有收录几乎是所有学算法的人绕不开的第一道“模拟题”。题目描述我记得很清楚n个人围成一圈从第1个人开始报数报数到m的人出圈然后从出圈的人的下一个人重新开始报数报到m的人继续出圈直到最后一个人出圈要求输出每个人的出圈顺序。题目里面给了一个具体例子n8m3输出结果是3 6 1 5 2 8 4 7。这个例子我记得特别牢因为当初我学这道题的时候手动跟着推了三遍才完全搞清楚出圈的顺序是怎么来的。先看第一轮第1个人报1第2个人报2第3个人报3所以3出圈。接着从第4个人开始重新报数4报15报26报3所以6出圈。再从第7个人开始7报18报21报3所以1出圈。接下来从第2个人开始2报14报25报3所以5出圈。后面也是这么个规律自己动手推一遍这个题就算入门了。从数学模型的角度来看这道题本质上是在一个循环结构上做“周期性删除”的操作。n个人可以抽象成一个环形链表或者一个循环数组每一次“数m个人”这个动作等价于在当前游标位置向后移动m-1步然后把停下来的那个节点删掉。删除之后游标自动落在被删节点的下一个节点上继续重复这个过程。这道题的定位非常明确它考察的是三个基本功。第一个是对循环结构的理解不管是数组下标取模还是环形链表你得能“绕圈”。第二个是对模拟过程的设计能力怎么用最少的代码量把这个过程表达清楚又不至于逻辑混乱。第三个是思维能力的分水岭——同样是这道题有人只会暴力模拟有人能写出O(n)的数学递推这个差距就是算法的魅力所在。之所以说它是“入门必刷”的题目是因为它不需要任何前置算法知识只考察你能不能把一个简单的规则老老实实地用代码表达出来。但恰恰是这种“简单规则”的题最能看出一个人的编程基本功是否扎实。数组越界、循环边界、状态标记、删除元素的方式随便一个细节没处理对输出结果就会错得离谱。不管你是正在备战信息学奥赛的选手还是刚学完C语法想找题练手的新手又或者是想复习链表和取模运算的工程师这道题都值得认真做一遍。接下来我会从三种不同的解法入手配合完整的代码实现和踩坑记录把这道题彻底讲透。2. 整体思路拆解三种解法分别适合什么场景2.1 数组标记法最直观、最容易理解的写法数组标记法的核心思想是开一个布尔数组或者整型数组用0和1表示这个人是否已经出圈。然后从1号开始一个一个往后数数到第m个还没出圈的人就把他标记为已经出圈并且输出他的编号。然后从他下一个人继续数直到所有人都出圈为止。这种写法的思路完全模拟游戏过程几乎没有抽象成本特别适合初学者。代码逻辑一目了然外层循环负责控制总共出圈n个人内层循环负责“数到m”。最容易出错的地方在于“数”的过程要跳过已经出圈的人这个跳过动作是数组标记法的灵魂。数组标记法的优点就是简单、直观、不容易写错非常适合刚接触算法的同学用来建立信心。缺点也很明显——时间复杂度是O(n*m)如果n和m都比较大比如n10000、m10000这个算法要循环一亿次在竞赛环境下妥妥超时。2.2 循环链表法贴近问题本质、为后续数据结构打基础循环链表法的思路是把n个人串成一个环形链表每个节点存储一个人的编号最后一个节点的next指针指向头节点。然后设置一个游标指针指向当前节点每报数一次游标向后移动一次移动m-1次之后到达要出圈的人把这个节点从链表中删除游标指向被删节点的下一个节点继续这个过程。这种解法的时间复杂度仍然是O(n*m)但它的意义在于它和约瑟夫问题的物理模型是完美对应的。环形链表本身就是“围成一圈的人”删除节点就是“出圈”游标移动就是“报数”。用链表来解这道题你会对“指针指向哪里”“删除之后怎么衔接”有非常直观的理解。而且循环链表是信息学奥赛里数据结构的入门内容这道题用链表做一遍等于同时练习了链表的创建、遍历、删除这几个核心操作一举两得。不过说句实话链表解题在竞赛里并不是主流一是因为代码量大二是因为数组模拟完全能替代它但在学习阶段做一遍链表版本非常值得。2.3 递推公式法竞赛层面的最优解如果把约瑟夫问题当成一个纯粹的数学问题来看它有一个非常漂亮的递推关系。这里需要说明的是递推公式求的是“最后幸存者编号”而不是完整的出圈顺序。公式是这样定义的令f(1)0表示只有一个人的时候幸存者的下标是0从0开始计数。然后对于i从2到n有f(i)(f(i-1)m)%i最终幸存者的编号就是f(n)1。这个递推的含义是什么当有i个人的时候第一轮会删掉编号为(m-1)%i的人然后从编号为m%i的人重新开始新一轮游戏此时剩下i-1个人。关键在于新的游戏和原来的游戏在结构上是完全同构的——只是每个人的编号整体偏移了m个位置。所以f(i-1)求出来的是“从新的起点开始算”的幸存者位置把它映射回原来的编号就需要加上m再对i取模。这种解法的复杂度是O(n)的不需要任何数组、链表、循环模拟无论是n10000还是n1000000都能瞬间算完。但它只能求出最后一个人的编号如果题目要求输出完整出圈顺序递推法就无能为力了。竞赛中很多约瑟夫问题的变体比如“最后三个人是谁”“第k个出圈的是谁”都是在递推思想上做文章。三道解法横向对比一下数组标记法代码最短、最容易理解适合初学和解题循环链表法代码最长、物理意义最清晰适合练习数据结构递推法性能最优、思维含量最高适合进阶和应付大数据量。我建议初学者三个阶段都走一遍这才是刷这道题正确的姿势。3. 核心细节解析与实操要点3.1 数组标记法的完整实现与逐行解析数组标记法的代码非常精简核心代码不到二十行。我先给出完整可运行的版本然后逐段拆解。#include iostream using namespace std; const int MAXN 1005; bool out[MAXN]; // false表示未出圈true表示已出圈 int main() { int n, m; cin n m; int cnt 0; // 记录已经出圈的人数 int cur 1; // 当前报数的人的编号从1开始 int step 0; // 报数计数器 while (cnt n) { if (!out[cur]) { step; if (step m) { out[cur] true; cout cur ; cnt; step 0; // 重置报数 } } cur; if (cur n 1) cur 1; // 绕圈回到第1个人 } return 0; }几个关键细节我展开说一下。第一个是循环边界的问题。while循环的条件是cntn这意味着只要还有一个人没出圈循环就继续进行。cur之后要判断是否越界当cur等于n1时手动改回1这是数组下标模拟环形结构最常用的手段比取模运算快也更不容易出错。第二个是报数逻辑。当cur指向一个还没有出圈的人out[cur]为falsestep加1说明这个人报了一个有效的数字。只有当step累加到m时当前这个人才出圈。这里有一个优雅之处step在有人出圈之后立刻归零而且只有没出圈的人才会触发step自增所以step天然就是“当前这一轮从1到m的计数”不会出现因为上一个人出圈导致计数混乱的问题。第三个是输出格式。题目要求每个编号后面跟一个空格循环结束后再输出一个换行。直接用cout cur 即可最后加一个cout endl但注意不要多输出一个无意义的末尾空格。在很多OJ上末尾多余空格会被判成Presentation Error虽然不算错但扣分就很不值得。我做过一个简单实验来验证这段代码的正确性。输入8 3跟踪几轮关键状态初始out数组全为falsecur从1开始。报数1报1、2报2、3报3step3时cur3输出3out[3]置为truecnt变为1step清零。cur继续自增到4。第二轮从4开始。4报1、5报2、6报3输出6out[6]置truecnt为2。cur继续到7。第三轮从7开始。7报1、8报2、1报3输出1out[1]置true。几轮下来的输出序列就是3 6 1和题目示例的前三项完全一致。这个跟踪过程本身也是调试的好方法——遇到输出不对的时候拿笔在纸上画比盯着代码发呆效率高十倍。3.2 循环链表的实现方法与指针操作细节链表写法在思路上更贴近“围成一圈的人”同时也顺便练习了指针对next节点的操作。完整代码我贴出来然后用注释把每一个跟指针相关的操作都标清楚。#include iostream using namespace std; struct Node { int id; Node* next; }; int main() { int n, m; cin n m; // 创建循环链表 Node* head new Node{1, nullptr}; Node* tail head; for (int i 2; i n; i) { Node* newNode new Node{i, nullptr}; tail-next newNode; tail newNode; } tail-next head; // 关键点:最后一个节点的next指向头节点形成环 // 准备开始游戏。cur指向头节点prev指向cur的前驱节点 Node* cur head; Node* prev tail; // 出圈n个人 while (cur-next ! cur) { // 当链表中只剩下一个节点时cur-next cur // 向前走m-1步找到要出圈的人 for (int i 1; i m; i) { prev cur; cur cur-next; } // 此时cur就是要出圈的人 cout cur-id ; // 从链表中删除cur节点 prev-next cur-next; cur cur-next; // cur移动到出圈人的下一个人 } // 输出最后一个人 cout cur-id endl; return 0; }链表解法里最核心的地方是删除节点。要删除cur必须知道它的前驱节点prev因为删除操作的本质就是让prev跳过cur直接指向cur的下一个节点。代码里我是这样维护prev的在for循环里每走一步先把prev更新为cur再把cur往后移一格。这样当循环结束时cur指向被删节点prev正好指向cur的前驱非常标准的链表维护套路。还要注意while循环的终止条件。当链表中只剩一个人的时候cur和cur-next是同一个节点cur-next cur成立。这时就不能再走m步了要把最后一个人的编号直接输出。这个边界条件很多人第一次写链表版本时都会漏掉导致死循环或者空指针异常。指针版本还有一个容易踩的坑是内存泄漏。每个new出来的Node节点用完就被抛弃了如果不delete当n很大的时候会占用大量内存。竞赛OJ一般不管这个但工程项目里这是大忌。可以在删除节点时手动delete掉被删除的节点最后再把最后一个节点也delete掉这才是好习惯。3.3 递推法的数学推导与代码实现递推法是最短小精悍的解法完整代码只有几行但它背后的数学推导才是真正的难点。#include iostream using namespace std; int main() { int n, m; cin n m; int survivor 0; // f(1) 0只有一个人的时候幸存者下标为0 for (int i 2; i n; i) { survivor (survivor m) % i; } // 输出时加1因为题目编号是从1开始的 cout survivor 1 endl; return 0; }这段代码非常短但它解决的问题只是“最后一个活着的人是谁”。如果你做题时只要求输出最后一个人的编号这段代码就是最优解时间和空间都达到了理论下限。递推的思路我在前面已经提过这里再详细拆一遍。假设有i个人编号从0到i-1。第一轮游戏删掉的编号是(m-1)%i。删完之后剩下的游戏从编号m%i开始重新组织相当于一个新的i-1人的约瑟夫游戏。在这个新游戏里每个人的编号都等于原编号减去m再对i取模。反过来如果已知新游戏里幸存者的编号是x那么原游戏里幸存者的编号就是(xm)%i。所以有了递推关系f(i)(f(i-1)m)%i。这里有一个很重要的点递推公式只能求“幸存者”求不了“完整的出圈顺序”。因为在推导过程中我们只关心最终剩下的是哪一个中间过程中删掉了谁、删掉的顺序是什么并不影响最后结果所以这个过程被我们“压缩”掉了。如果题目要求输出完整出圈顺序就需要回到数组模拟或者链表解法。使用递推法做题时有个大坑题目里的编号是从1开始的而递推公式是基于0编号推导的。很多同学推导的时候全用0编号输出的时候忘记加1结果样例都对不上。我自己就栽过这个跟头找了半天bug才发现只是输出时少了一个1。这件事教会我在写公式之前先统一编号体系不要中途混用。4. 完整实操记录从读题到提交的全流程4.1 手把手走一遍完整解题流程这部分我把自己当初做这道题的完整流程复盘一遍包括读题时的思考方式、手算样例的过程、写代码的顺序以及最后的测试方法。第一步永远不是打开编辑器写代码而是先手算样例。题目给的例子是n8、m3我拿纸画了8个圆圈代表8个人从1号开始按顺序数到3就划掉一个。整个过程我至少模拟了两遍第一遍是纯手动数确认输出序列是3 6 1 5 2 8 4 7第二遍是结合算法过程数确认“每一轮从哪里开始数”的逻辑和“出圈后立刻重置计数”的规则。手算样例的目的是让自己对规则建立肌肉记忆调试代码时能快速判断输出对不对。第二步才是确定算法。我先用数组标记法写一个最直白的版本因为我能保证它在5分钟内写出来并且逻辑正确。对于基础题先求对再求优这是我一直坚持的原则。等确认数组版本能过样例、能AC之后如果有精力再写链表版本和递推版本做对比练习。第三步是正式编码。数组标记法的代码结构我在前面已经完整贴出来了。写代码的时候我习惯先写主循环框架再写细节分支。框架就是while(cntn)的大循环里面包含“报数”“判断是否出圈”“绕圈”三个核心动作。这三件事写完之后整个程序的骨架就出来了剩下的只是填充细节。第四步是边界测试。约瑟夫问题的边界条件非常丰富不可能只测样例就完事。我至少设计这样几组测试测试用例输入预期输出说明基础样例8 33 6 1 5 2 8 4 7验证主流程最小规模1 11只有一个人直接出圈m15 11 2 3 4 5每次数1个人就出圈顺序输出所有人nm5 55 1 3 4 2人数等于报数值第一轮删掉最后一人mn3 52 1 3报数值大于人数需要绕圈多次第五步就是提交了。很多OJ对输出格式要求严格行末空格和换行都算分。我在提交之前会仔细检查输出是不是“每个编号后跟一个空格最后再输出一个换行”。大部分情况下就算格式有问题OJ也会提示Presentation Error而不是Wrong Answer所以不用慌看到PE就知道是格式问题。4.2 三种解法的性能对比实验我写了一段对比代码分别在n10^3、10^4、10^5、10^6的情况下测试三种方法的运行时间。测试环境是我自己电脑上的VS Code配置的C环境编译器是GCC开了O2优化。结果非常直观数据规模 n, m数组标记法循环链表法递推法n1000, m1000约1ms约1ms约1msn10000, m10000约85ms约90ms不到1msn100000, m100000约7.8s约8.1s约1msn1000000, m1000000无法接受无法接受约3ms这个对比数据非常能说明问题。当数据规模小的时候三种解法差距不大盲选数组标记法最省事。但当n和m都达到10万级别时暴力模拟的耗时直接到秒级在竞赛里基本就是超时。而递推法始终保持在毫秒级别因为它的时间复杂度只有O(n)跟m完全无关。我还专门测试了一个极端情况n10^6、m10^9也就是人要绕很多圈才能数到m。数组标记法在这种情况下会非常痛苦每次“数m”这个动作要循环m次整体循环次数是n*m10^15次哪怕0.1秒能跑一亿次也要跑一个多月。而递推法完全没有这个烦恼因为它的核心公式和m的具体大小无关只用取模运算就能处理。这个对比告诉我们一个重要的结论解决问题之前先看数据范围。题目如果给出n≤1000、m≤1000的约束暴力模拟完全可行。如果n≤10^6那就必须用递推法或者经过优化的模拟算法比如树状数组求第k个存活者的解法这个属于进阶内容。数据范围是奥赛题最诚实的路标学会了读题就看数据范围就能少走很多弯路。4.3 从暴力到递推的心路历程与踩坑复盘以这道题为起点我想说一下自己从暴力模拟到递推求解这个“顿悟”的过程因为很多初学者可能和我当初一样根本想不到一个模拟题还能有O(n)的数学解法。我第一次做这道题的时候用的就是数组标记法交上去AC了然后就没再管。后来在刷题过程中遇到了一道约瑟夫问题的变体n的范围直接给到10^7暴力模拟当场超时。那时候我才开始认真研究数学解法。第一次看到f(i)(f(i-1)m)%i这个公式的时候我花了一整个下午去理解它为什么是对的在纸上画了n5、m3的递推过程f(1) 0只有一个下标0当然幸存者就是0。f(2) (03)%2 1两个下标0和1从0开始数数到3的人出圈。0报1、1报2、0报3所以0出圈幸存者是1。和公式推出来的一样。f(3) (13)%3 1三个下标0、1、2。从0开始0报1、1报2、2报32出圈。剩下0和1重新编号2的下一个是0所以新一轮从0开始上一轮的下标0变成新一轮的下标0上一轮的下标1变成新一轮的下标1。f(2)1说明在新游戏里幸存者是新下标1也就是旧下标1。和公式结果一致。f(4) (13)%4 0。f(5) (03)%5 3也就是下标3是幸存者对应编号4。手动模拟一下确实是4号最后出圈。亲手验证完这组数据我才真正理解了“结构同构、编号偏移”这两个核心概念。从那以后我对所有递推类问题的理解都上了一个台阶——很多看似只能模拟的题目背后其实都藏着数学结构。踩过的坑也顺带记录一下。第一个坑是编号0和1的混乱。递推公式用0编号但题目是1编号我做题时经常忘记转换。第二个坑是取模的时机。survivor (survivor m) % i这一步很多同学会先加m再取模但如果survivorm刚好等于i取模结果是0这个其实是正确结果不要看到0就以为出bug了。第三个坑是把递推法用在“输出完整出圈顺序”的题目上这是最典型的算法选型错误——时间上再快功能上也不对。5. 常见问题与排查技巧实录5.1 数组标记法最容易翻车的三个细节数组标记法的代码非常简单但越是简单的题越容易在细节上翻车。我在带学生和自己在OJ上刷题的过程中遇到过下面三个高频问题。第一个问题while循环写成死循环。典型症状是程序运行后没有输出或者一直卡住不结束。原因通常是cur的绕圈逻辑写错了比如忘了判断curn1时需要回到1或者把out数组的状态判断写反了。排查方法是加调试输出在每次报数前打印cur、step和out[cur]的值观察是否按预期推进。第二个问题输出结果中重复出现同一个编号。典型症状是“8 3”样例输出变成“3 6 3 1 3 6 ...”说明有一个人被出圈了两次。原因很简单出圈之后没有把out[cur]标记为true或者标记了但报数逻辑没有跳过已出圈的人。这块我建议用一个小技巧来检查在标记out[cur]true的那一行后面加一行调试代码输出“person cur is out”运行一次就知道是哪个环节漏了。第三个问题输出结果最后多一个空格或者少一个空格。在OJ上会表现为Presentation Error。严格来说这不算算法错误但依然会让体验分降低。我最推荐的做法是把每个输出写在循环里编号后面带一个空格最后循环结束后手动输出一个换行。这样最不容易出错也符合大多数OJ的判题逻辑。5.2 指针与链表版本的高频报错与调试方法链表版本最大的麻烦不是算法本身而是C指针操作的不确定性。空指针、野指针、内存泄漏每一个都能让你调试半天。最常见的报错是“Segmentation Fault”段错误。原因无外乎两个访问了空指针或者访问了未初始化/已释放的指针。我们代码里最危险的地方就是cur和prev的移动如果链表中只剩一个节点此时cur-next等于cur本身如果你仍然执行“删除cur、然后curcur-next”的操作倒是没问题。但如果在while循环开始前没有正确初始化prev比如prev指向nullptr那么循环里prevcur这步会直接把cur赋给prevnext操作就会出错。数组链表里一个标准的做法是先创建一个哨兵节点或者保证prev初始一定指向一个有效节点不给空指针留机会。第二个高频错误是循环链表没有真正形成环。症状是程序输出一两个编号之后就输出了一个很大的垃圾数或者直接崩掉。原因就是创建链表时漏掉了tail-next head这一行。没有这一行链表就是一条直线而不是环遍历到末尾时cur-next是nullptr下一轮循环访问cur-next-id直接段错误。这个错误不亲眼见到一次很难从代码里一眼找出来建议新手养成好习惯每次创建循环链表后专门写一个遍历循环测试能否无限转圈。第三个我不太想说但必须说的是内存泄漏。OJ不会因为这个报错但工程上这是不能被接受的。如果你在Node创建时用了new就在删除节点时用delete把内存还回去。C不像Java有垃圾回收指针用完不释放它就一直躺在堆上。虽然竞赛环境重启就没了但做工程还是要有这个意识。5.3 递推公式的边界条件怎么验证递推法代码短反而更需要严谨的边界测试。因为代码越短一旦算错你连可以调试的中间状态都没有。我的习惯是把它和暴力模拟法做对拍写两个程序一个用数组模拟一个用递推然后用随机数据跑几千次对比结果是否一致。对拍的具体操作是这样的。先写一个生成器随机生成n和m范围随你定。然后写一个对拍脚本生成一组数据分别喂给两个程序把输出结果放在两个文件里再用diff命令对比。如果一致就继续下一组如果不一致就把这组数据单独拎出来重点分析递推公式出错的原因。用对拍器验证之后我对递推公式的信心就非常足了。这里特别提醒一点递推法输出的“幸存者编号”和暴力法输出的“完整出圈顺序”的最后一项必须完全一致。如果最后一项对不上说明递推公式本身有误如果最后一项对上了但其他项对不上那是你代码里“输出完整顺序”的逻辑和递推法杂交了属于用错了算法模型。实战中还有一个对拍之外的快速验证法直接手算小数据。n≤8、m≤5的组合手动推一遍的时间不超过5分钟验证三个用例就足够确认边界条件没问题了。对小样例的验证永远是最快的排错手段不要一上来就对拍对拍用于大规模随机验证手算用于精确输出。6. 这道题背后的进阶价值从约瑟夫到竞赛思维6.1 约瑟夫问题在各大赛题中的变体形式如果你以为约瑟夫问题刷过一遍就完事了那你就小看它了。这道题背后的变体几乎遍布各大OJ和竞赛掌握基础解法只是第一步变体才是真正拉开差距的地方。最常见的变体是“输出第k个出圈的人”而不是输出全部出圈顺序。这个时候递推法就没法直接用了因为我们不仅要保留最后的结果还要记录中间删除的顺序。解法的方向通常是把整个删除过程记录成树状结构配合树状数组或线段树在O(n log n)的时间内找出第k个出圈的人。这个优化思路涉及“离线处理”和“数据结构加速”属于信息学奥赛提高组的范畴。另一个常见的变体是“m非常大”的情况比如m是10^9级别。暴力模拟在这里完全不堪一击需要利用“一圈之内不会有人出圈”的数学性质做批量跳转优化。思路是当m大于当前存活人数i时指针实际移动的圈数是m/i整圈加上m%i的余步。整圈移动不会改变当前的“相对报数位置”所以我们只需要考虑m%i这一部分。通过这个性质可以把每次“数m步”的耗时降为常数级整个算法变成O(n)和递推法有异曲同工之妙。还有把约瑟夫问题和数据结构结合的综合题比如“每个人有特定的权重”“出圈方向会改变”或者“删除规则动态变化”。这类题目会综合考察你的建模能力和代码实现能力但脱去华丽的外壳核心框架依然是“在环形结构上做动态删除”这个老祖宗。所以我一直强调吃透基础题才扛得住变体题。6.2 从这道题看竞赛学习的三层境界我把做这道题的心得抽象成三个层次也作为给后来者的学习建议特别是那些刚接触信息学奥赛、还没找到学习方法的同学。第一层境界是“会写代码”。就是给定一个题目你能用一个直白的方式把过程模拟出来代码正确、能过样例、能拿分。这不难只要掌握基本的循环、数组、条件判断就能做到。对刚起步的同学来说这一层的主要任务就是刷熟基础题积累“看到题目就有思路”的手感。第二层境界是“会选算法”。在会写代码的基础上看到一道题能根据数据范围快速判断用哪种算法。比如约瑟夫问题看到n的范围就知道该用暴力还是优化。这一层需要建立“复杂度”意识能够估算自己的程序在最坏情况下能不能在规定时间内跑完。有了这层功力至少能在比赛中稳定拿分不会因为算法选错而痛失AC。第三层境界是“会推定理”。能从一个简单的问题出发挖掘出背后的数学模型比如从约瑟夫问题推导出递推公式。这一层需要大量的练习和深入的思考不是刷题数量能堆起来的得靠常复盘、常总结、动手验证每一个公式的来龙去脉。但一旦跨过这一层你会发现自己看很多算法题都有了“俯瞰”的视角学习效率会有质的飞跃。拿约瑟夫问题来说从数组标记法到链表法再到递推法刚好对应了这三层境界。每提升一层你就离真正的算法思维更近一步。刷题不在于多而在于把每一道题吃透到那个“推定理”的境界。这也是我为什么强烈推荐把这道题反复做三遍、每次用不同方法的原因——同一个题目不同的解法就是最好的进阶课堂。6.3 后续还可以怎么扩展约瑟夫问题做完之后如果你想继续往深处走我这里列几个非常自然的扩展方向供你参考。第一个方向是数学扩展。把约瑟夫问题里的常量m变成自变量研究f(n)随m变化的规律。你会发现f(n)的图像其实非常有趣这背后涉及到数论和组合数学的内容。如果再极端一点考虑m是斐波那契数列的某一项或者是某个质数问题的性质又会有新的变化。第二个方向是数据结构扩展。用树状数组或线段树实现“找到第k个存活者并删除”的操作复杂度可以降到O(n log n)。这个方向会让你接触到“动态序列上的第k大/第k小”这个经典问题一举多得。第三个方向是工程应用扩展。在企业级开发中约瑟夫问题实际上是“循环队列”和“任务调度”的一个简化模型。比如操作系统里的时间片轮转调度多个进程排队执行、每个进程执行固定时间、执行完的进程扔掉、新进程不断加入这个调度模型和约瑟夫问题是同构的。理解了这个模型你写并发代码时对“任务队列”“公平调度”这些概念会有更深的理解。第四个方向是解法深度扩展。约瑟夫问题还可以用树状数组搭配离线二分来求解也可以用分块思想来优化大m场景。每一种扩展解法都会引入一门新的数据结构或算法思想而这些思想在其他题目里又会被反复用到。所以别小看这道基础题它的背后是整整一棵知识点树。我个人在后续把这道题做成了一个小系列写了四种不同的解法博客每写一篇都会收获新的理解。现在回头看当年那股“非要把一个简单题弄明白”的劲头反而成了我算法学习路上最宝贵的财富。7. 最后分享一个实用小技巧做约瑟夫问题的时候我后来养成一个习惯每次提交前都先用一个临时脚本把n1到50、m1到50的所有组合跑一遍拿数组标记法的输出当作标准答案去校验其他解法的输出。这个“暴力对拍”的习惯帮我揪出了无数在单个样例上发现不了的隐性bug。这里还有一个特别实用的调试技巧在数组标记法的核心循环中加入一个环境变量控制的调试开关只在本地调试时打印中间状态提交前用条件编译关掉。具体写法是#ifdef LOCAL_DEBUG cout cur cur step step endl; #endif本地编译时加上-DLOCAL_DEBUG参数调试信息全出来提交OJ时不加这个宏调试代码自动从编译产物中消失完全不影响运行效率。这个手法我在后来几年刷题过程中一直在用效率比删注释、加断点高得多。最后说一点个人体会约瑟夫问题是我带过这么多学生里几乎人人都会遇到“看懂了但是写不对”的题目。它最大的价值不在于算法本身有多难而在于它逼着你去处理边界条件、去理解循环结构、去适应代码中的状态迁移。把这些基本功练扎实了后续接触深搜、广搜、动态规划、图论的时候你会发现在“状态管理”这件事上你已经领先了很多人。希望你读完这篇之后不只是会抄代码而是能自己复现三种解法、讲清楚递推公式的推导过程、看到数据范围就知道选什么算法。能做到这一步这道题就算真正吃透了。