博主名称_Doubletful大家好欢迎来到Doubletful的博客博主的GitHub Go to git_hub算法专栏路漫漫其修远兮吾将上下而求索文章目录来源前言一、题目二、构建环形链表0.5-链表结点的结构1-环形链表构建函数三、方法解析0.5-主操作函数1-传统解法1.2-代码1.4-内循环遍历例图1.6-外循环删除m节点例图1.8-最后一次删除m节点例图2-单层计数解法2.2-代码2.4-循环遍历例图2.6-循环删除m节点例图2.8-最后一次删除m节点例图3-合并演变解法四、三种方法对比总结表五、数学优化思考1-当前时间复杂度分析2-当前空间复杂度分析3-数学解法递推公式0.5-代码1-复杂度对比4-选择建议六、练习来源约瑟夫环问题Josephus Problem源于一个古老而悲壮的传说。公元1世纪犹太历史学家弗拉维奥·约瑟夫斯Flavius Josephus在一次战争中被罗马军队围困在山洞中。他和40名犹太士兵宁死不降决定围成一圈按规则自杀从第一个人开始报数每数到第3个人就将其处决然后下一个人重新从1报数如此循环直到只剩一人。约瑟夫斯和一位朋友不想死他们通过快速计算站在了最后幸存的位置上分别是第16位和第31位最终投降活了下来。这个“幸存者问题”后来被抽象为数学问题成为算法和数据结构中经典的循环链表或递推案例。前言本博客将使用C语言讲解约瑟夫环算法聚焦链表模拟法通过三种不同风格代码的对比展示设计的巧妙拓展的重要理念循环不变量一、题目此界面源自牛客网——从描述中能看出此题目的问题就相当于一个不断判断条件的环形数组的遍历但使用数组实现还需使用取余操作避免越界同时删除元素极不便利因此采用环形链表实现。示例中的人数序列号从1开始当遍历到第m个人时使其出队删除之后从第m 1个人开始继续判断直到总人数为1时返回该约瑟夫环的人数序列号二、构建环形链表如果题目已给出一个环形链表此段可跳过0.5-链表结点的结构注代码部分如果直接复制不能成功运行请将所有中文前的#替换为//#定义时直接声明名称typedefstructListNode{intval;#存储值structListNode*next;#指向下一个节点的指针}LN;1-环形链表构建函数LN*CreateCircle(intn){#头节点 LN*head(LN*)malloc(sizeof(LN));head-val1;#尾节点 LN*tailhead;for(inti2;in;i){#新节点 LN*node(LN*)malloc(sizeof(LN));node-vali;#利用尾链接新节点 tail-nextnode;tailtail-next;}#闭环 tail-nexthead;returntail;}——首先初始化头节点并创建尾节点用于链接和遍历所有的中间节点且最后还需尾节点使链表链接成环。因为每个结点的值为人数序列号并且从1开始计数因此在创建头节点后使 i 初始化为2直到 i 为 n 终止可能产生的疑问为什么返回尾节点答方便在删除操作中快速获取前驱节点三、方法解析0.5-主操作函数intysf(intn,intm){returnLastNum(CreateCircle(n),m);}——参数 n 为人数即链表结点个数参数 m 为从 1 开始计数数到 m 的退出规则将 n 传入环形链表构建函数然后将返回值链表头结点的前一个结点即尾节点和 m 传入计算最后一个人编号的函数最后将结果返回。注如果题目已给定环形链表需遍历环形链表找到尾节点后将尾节点传入计算函数遍历的判断条件为 cur-next ! head*1-传统解法1.2-代码intLastNum(LN*prev,intm){#初始化cur为头节点 LN*curprev-next;#持续遍历计算while(cur!prev){for(inti1;im;i){prevprev-next;curcur-next;}prev-nextcur-next;free(cur);curprev-next;}#返回最后一个节点的值returncur-val;}1.4-内循环遍历例图1.6-外循环删除m节点例图1.8-最后一次删除m节点例图——初始化 cur 为 prev 的 next也就是初始化为链表的头节点使其与尾节点的步长在环内永远差一遍历环在环内使用另一个循环报数由于 cur 为头节点从报数逻辑来看已完成报数因此 i 初始化为1每次内循环令 cur 走 m - 1步。当内循环执行时其内部逻辑使 prev 为 cur 的前驱结点使其步长永远保持差一。每次当内循环完成遍历时cur 已指向第 m 个人此时执行删除操作首先让 prev 指向的下一个从 cur 修改为 cur 指向的下一个防止断链其次释放 cur 的空间删除节点最后让 cur 等于 prev 的下一个节点使其步长保持差一。持续循环遍历链表当链表删除到只剩一个节点时prev 的下一个指向的节点必然为其本身而 cur 一直都是 prev 的下一个节点所以循环的结束条件为 cur ! prev*2-单层计数解法2.2-代码intLastNum(LN*prev,intm){#初始化cur为尾节点 LN*curprev;intcnt0;#持续遍历计算while(cur!cur-next){if(cntm){prev-nextcur-next;free(cur);curprev;cnt0;}prevcur;curcur-next;cnt;}#返回最后一个节点的值returncur-val;}2.4-循环遍历例图2.6-循环删除m节点例图2.8-最后一次删除m节点例图——此解法首先初始化 cur 为尾节点使其与尾节点的步长在环内永远一致去除内层循环并添加了计数器 cnt当计数器不等于 m 时执行链表遍历操作相当于解法一内循环的作用特判等于 m 的情况执行删除操作当只剩一个元素时返回其值。此解法循环的结束条件虽然有发生变化但本质不变无论是 cur ! prevcur ! cur-next 或 prev ! prev-next 都利用了最后只剩一个节点时 prev 或 cur 的指针指向其本身的逻辑。注意此解法不能使用cur ! prev 作为结束条件执行细节由于初始化 cur 为头结点的前一个结点从报数逻辑来看当前为0因此cnt 从0开始计数cur 从 prev 开始走当等于 m 时恰好走 m 步注意需先判断再将计数器累加过程为从0至 m - 1 步不进入特判等于 m 时进入此时执行删除操作后将 cur 等于 prev使其步长保持一致并将 cnt 重新初始化为03-合并演变解法intLastNum(LN*prev,intm){#初始化cur为尾节点 LN*curprev;#持续遍历计算while(cur!cur-next){for(inti1;im;i){prevcur;curcur-next;}prev-nextcur-next;free(cur);curprev;}#返回最后一个节点的值returncur-val;}——此解法的执行过程(框架)沿用了传统解法执行逻辑(内核)沿用了单层计数解法省去计数器 cnt 使代码简洁易读。cur 初始化为尾节点需走 m 步后执行删除操作每次模拟从1报到 m 后离开的过程此为循环不变量四、三种方法对比总结表维度方法一传统 m-1步方法二单层计数器方法三移动 m步内层循环有 for 循环无外层单层有 for 循环每次移动步数m-11累加m初始化 curprev-next头结点prev尾节点prev尾节点删除后 cur 赋值prev-nextprevprev计数器无cnt 显式管理无时间复杂度O(n*m)O(n*m)O(n*m)空间复杂度O(1)O(1)O(1)五、数学优化思考1-当前时间复杂度分析外层循环次数分析 n需要删除 n - 1 个节点只剩最后一人每次删除对应一次外层循环迭代内层移动次数分析 m方法一传统解法每次删除前需要移动 m-1 步找到第 m 个节点方法二单层计数器通过 cnt 累加每 m 步执行一次删除方法三合并演变每次删除前需要移动 m 步总操作次数每次删除都需要接近 m 次移动总移动次数约为 (n-1)* m因此时间复杂度为 O(n*m)当 m 等于 n 时使复杂度退化为O(n²)2-当前空间复杂度分析三种方法的空间复杂度均为O(1)原因如下额外空间使用算法只使用了固定数量的指针变量prev、cur、cnt 等这些变量的数量与输入规模 n 无关。链表本身空间链表节点的空间 O(n) 是输入数据的一部分不计入算法额外空间复杂度。递归/栈空间算法采用迭代实现没有使用递归调用不占用栈空间。3-数学解法递推公式对于约瑟夫环问题存在时间复杂度为O(n)的数学递推解法0.5-代码intysf(intn,intm){intresult0;for(inti2;in;i){result(resultm)%i;}returnresult1;}递推公式f(nm) (f(n - 1m) m) % n核心逻辑已知小规模下的人数编号“新编号”计算出大规模下的人数编号“原编号”。递推公式从最后一个确定的新编号f(1) 0 出发不断求出上一轮对应的原编号即更大规模下的编号直到得到人数为 n 的编号。执行细节i 代表当前人数当 i 为1时不需要遍历求值因为最后一个人的编号已知因此直接让循环从人数为2的轮次求上一轮的编号直到 i 为 n 时当前求出的编号就为最后一个人对应到人数为 n 时的编号。设最后一个人在当前轮次中的编号从0开始报数便于取模计算。最后返回结果时将编号0 ~ n - 1转换为从1开始的编号1 ~ n1-复杂度对比1.时间复杂度O(n)只需一次循环2.空间复杂度O(1)只使用常数个变量3.优势当 n 和 m 很大时数学解法效率远高于链表模拟4-选择建议1.面试或教学中展示链表模拟法体现算法思维2.竞赛或工程中优先使用数学递推法3.特殊需求时根据具体场景选择合适的数据结构六、练习由于数学解法即为模拟解法的反推如同编程中的递归思想请根据数学解法中的递推公式写出约瑟夫环的递归解法十分感谢你的阅读本期不确定如何更详实的介绍算法使其内容缩减而非略显臃肿