Golang学习-约瑟夫环问题（Josephus Problem）

约瑟夫环问题Josephus Problem一、问题描述约瑟夫环是一个经典的数学与计算机科学问题。其情景如下N 个人围成一圈编号 1~N。从编号 1 开始报数报到 M 的人出列下一位从 1 重新开始报数再报到 M 的人出列……如此循环直到只剩最后一人。求最后幸存者的原始编号。这个问题的历史可以追溯到公元 1 世纪犹太历史学家约瑟夫Flavius Josephus在罗马围攻中与 40 名同胞藏身洞穴他们决定宁可自杀也不做俘虏。约瑟夫通过数学计算站到了幸存位置——他自述的这段经历便成了这个问题的名称。二、三种解法对比解法时间复杂度空间复杂度特点数组模拟法O(n × m)O(n)直观易懂但慢循环链表模拟法O(n × m)O(n)贴合问题本质但同样慢递推公式法O(n)O(1)最优解纯数学推导三、解法一数组模拟法用一个[]int表示还在圈中的人1表示在场0表示已出列。从头到尾循环扫描遇到未出列的人就计数数到 m 时标记出列。3.1 实现思路初始化数组所有位置标记为 1在场遍历数组对在场的人报数报到 m 时标记出列计数器归零当出列人数 n-1 时停止剩下那个就是幸存者3.2 代码packagemainimportfmt// JosephusArray 数组模拟法funcJosephusArray(n,mint)int{ifn0||m0{return-1}alive:make([]bool,n)// true在场fori:rangealive{alive[i]true}count:0// 已出列人数number:0// 报数器idx:0// 当前下标forcountn-1{ifalive[idx]{numberifnumberm{alive[idx]false// 出列number0count}}idx(idx1)%n// 环形绕回}// 找到唯一幸存者fori,a:rangealive{ifa{returni1// 编号从 1 开始}}return-1}funcmain(){fmt.Println(n41, m2:,JosephusArray(41,2))// 19fmt.Println(n8, m5:,JosephusArray(8,5))// 3fmt.Println(n5, m3:,JosephusArray(5,3))// 4}运行结果n41, m2: 19 n8, m5: 3 n5, m3: 4缺点每次循环都要跳过已出列的人时间复杂度为 O(n × m)当 n 和 m 都很大时效率很低。四、解法二循环链表模拟法用循环链表直接模拟围成一圈的场景每报到 m 就删除当前节点天然贴合问题模型。4.1 代码packagemainimportfmttypeCLNodestruct{NointNext*CLNode}// JosephusCircularList 循环链表模拟法funcJosephusCircularList(n,mint)int{ifn0||m0{return-1}// 构建循环链表1 - 2 - ... - n - 1head:CLNode{No:1}cur:headfori:2;in;i{cur.NextCLNode{No:i}curcur.Next}cur.Nexthead// 尾指头形成环// 找到头节点的前驱辅助删除prev:headforprev.Next!head{prevprev.Next}// 开始报数每次报 m 个人就删除forcur.Next!cur{// 直到只剩一个人// 报数 m-1 次当前节点算第1个走 m-1 步到第 m 个fori:1;im;i{prevcur curcur.Next}// 删除 cur 节点prev.Nextcur.Next curcur.Next}returncur.No}funcmain(){fmt.Println(n41, m2:,JosephusCircularList(41,2))// 19fmt.Println(n8, m5:,JosephusCircularList(8,5))// 3fmt.Println(n5, m3:,JosephusCircularList(5,3))// 4}运行结果n41, m2: 19 n8, m5: 3 n5, m3: 4优点模型直观不需要额外的标记数组缺点时间复杂度仍然是 O(n × m)空间复杂度 O(n)五、解法三递推公式法最优解这是约瑟夫问题的数学精华。通过递推关系可以做到 O(n) 时间、O(1) 空间。5.1 推导过程设f(n, m)表示 n 个人、报数为 m 时最后幸存者的编号从 0 开始编号。基本情况当 n 1 时只有一个人幸存者就是 0 号。f(1, m) 0递推当 n 个人中第一个出列的是第 m 个人编号 m-1后剩下 n-1 个人。关键在于这 n-1 个人的编号体系发生了偏移原始编号: 0, 1, 2, ..., m-2, m-1, m, m1, ..., n-1 出列后: m, m1, ..., n-1, 0, 1, ..., m-2 重新编号: 0, 1, ..., n-m-1, n-m, n-m1, ..., n-2从原始编号到新编号的映射关系新编号 (旧编号 - m) % n 旧编号 (新编号 m) % n所以f(n, m) (f(n-1, m) m) % n这就是约瑟夫问题的核心递推公式5.2 从 0 编号到 1 编号上述公式假设编号从 0 开始。如果要从 1 开始编号最终结果加 1 即可result f(n, m) 15.3 代码实现packagemainimportfmt// JosephusRecursive 递归版本可能栈溢出n 大时不推荐funcJosephusRecursive(n,mint)int{ifn1{return0}return(JosephusRecursive(n-1,m)m)%n}// JosephusIterative 迭代版本推荐O(n) 时间 O(1) 空间funcJosephusIterative(n,mint)int{ifn0||m0{return-1}survivor:0// f(1, m) 0fori:2;in;i{survivor(survivorm)%i}returnsurvivor1// 转为 1~n 编号}funcmain(){fmt.Println(n41, m2:,JosephusIterative(41,2))// 19fmt.Println(n8, m5:,JosephusIterative(8,5))// 3fmt.Println(n5, m3:,JosephusIterative(5,3))// 4fmt.Println(n1000000, m3:,JosephusIterative(1000000,3))// 大规模也能秒出}运行结果n41, m2: 19 n8, m5: 3 n5, m3: 4 n1000000, m3: 3744335.4 手动验证递推过程以 n5, m3 为例编号 0~4isurvivor计算10f(1)02(03)%2 1f(2)3(13)%3 1f(3)4(13)%4 0f(4)5(03)%5 3f(5)最终 survivor 3转为 1 编号 4。验证正确六、扩展出列顺序如果不仅要求最后幸存者还要知道每个人的出列顺序递推公式就不够了需要模拟。循环链表法可以轻松记录出列顺序funcJosephusOrder(n,mint)[]int{ifn0||m0{returnnil}// 构建循环链表head:CLNode{No:1}cur:headfori:2;in;i{cur.NextCLNode{No:i}curcur.Next}cur.Nexthead prev:headforprev.Next!head{prevprev.Next}varorder[]intforcur.Next!cur{fori:1;im;i{prevcur curcur.Next}orderappend(order,cur.No)prev.Nextcur.Next curcur.Next}orderappend(order,cur.No)// 最后幸存者returnorder}