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

约瑟夫环问题（Josephus Problem）

一、问题描述

约瑟夫环是一个经典的数学与计算机科学问题。其情景如下：

N 个人围成一圈，编号 1~N。从编号 1 开始报数，报到 M 的人出列；下一位从 1 重新开始报数，再报到 M 的人出列……如此循环，直到只剩最后一人。求最后幸存者的原始编号。

这个问题的历史可以追溯到公元 1 世纪，犹太历史学家约瑟夫（Flavius Josephus）在罗马围攻中与 40 名同胞藏身洞穴，他们决定宁可自杀也不做俘虏。约瑟夫通过数学计算站到了幸存位置——他自述的这段经历便成了这个问题的名称。

二、三种解法对比

三、解法一：数组模拟法

用一个[]int表示还在圈中的人，1表示在场，0表示已出列。从头到尾循环扫描，遇到未出列的人就计数，数到 m 时标记出列。

3.1 实现思路

1. 初始化数组，所有位置标记为 1（在场）
2. 遍历数组，对在场的人报数
3. 报到 m 时标记出列，计数器归零
4. 当出列人数 = n-1 时停止，剩下那个就是幸存者

3.2 代码

packagemainimport"fmt"// JosephusArray 数组模拟法funcJosephusArray(n,mint)int{ifn<=0||m<=0{return-1}alive:=make([]bool,n)// true=在场fori:=rangealive{alive[i]=true}count:=0// 已出列人数number:=0// 报数器idx:=0// 当前下标forcount<n-1{ifalive[idx]{number++ifnumber==m{alive[idx]=false// 出列number=0count++}}idx=(idx+1)%n// 环形绕回}// 找到唯一幸存者fori,a:=rangealive{ifa{returni+1// 编号从 1 开始}}return-1}funcmain(){fmt.Println("n=41, m=2:",JosephusArray(41,2))// 19fmt.Println("n=8, m=5:",JosephusArray(8,5))// 3fmt.Println("n=5, m=3:",JosephusArray(5,3))// 4}

运行结果：

n=41, m=2: 19 n=8, m=5: 3 n=5, m=3: 4

缺点：每次循环都要跳过已出列的人，时间复杂度为 O(n × m)，当 n 和 m 都很大时效率很低。

四、解法二：循环链表模拟法

用循环链表直接模拟"围成一圈"的场景，每报到 m 就删除当前节点，天然贴合问题模型。

4.1 代码

packagemainimport"fmt"typeCLNodestruct{NointNext*CLNode}// JosephusCircularList 循环链表模拟法funcJosephusCircularList(n,mint)int{ifn<=0||m<=0{return-1}// 构建循环链表：1 -> 2 -> ... -> n -> 1head:=&CLNode{No:1}cur:=headfori:=2;i<=n;i++{cur.Next=&CLNode{No:i}cur=cur.Next}cur.Next=head// 尾指头，形成环// 找到头节点的前驱（辅助删除）prev:=headforprev.Next!=head{prev=prev.Next}// 开始报数，每次报 m 个人就删除forcur.Next!=cur{// 直到只剩一个人// 报数 m-1 次（当前节点算第1个，走 m-1 步到第 m 个）fori:=1;i<m;i++{prev=cur cur=cur.Next}// 删除 cur 节点prev.Next=cur.Next cur=cur.Next}returncur.No}funcmain(){fmt.Println("n=41, m=2:",JosephusCircularList(41,2))// 19fmt.Println("n=8, m=5:",JosephusCircularList(8,5))// 3fmt.Println("n=5, m=3:",JosephusCircularList(5,3))// 4}

运行结果：

n=41, m=2: 19 n=8, m=5: 3 n=5, m=3: 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, m+1, ..., n-1 出列后: m, m+1, ..., n-1, 0, 1, ..., m-2 重新编号: 0, 1, ..., n-m-1, n-m, n-m+1, ..., 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) + 1

5.3 代码实现

packagemainimport"fmt"// JosephusRecursive 递归版本（可能栈溢出，n 大时不推荐）funcJosephusRecursive(n,mint)int{ifn==1{return0}return(JosephusRecursive(n-1,m)+m)%n}// JosephusIterative 迭代版本（推荐，O(n) 时间 O(1) 空间）funcJosephusIterative(n,mint)int{ifn<=0||m<=0{return-1}survivor:=0// f(1, m) = 0fori:=2;i<=n;i++{survivor=(survivor+m)%i}returnsurvivor+1// 转为 1~n 编号}funcmain(){fmt.Println("n=41, m=2:",JosephusIterative(41,2))// 19fmt.Println("n=8, m=5:",JosephusIterative(8,5))// 3fmt.Println("n=5, m=3:",JosephusIterative(5,3))// 4fmt.Println("n=1000000, m=3:",JosephusIterative(1000000,3))// 大规模也能秒出}

运行结果：

n=41, m=2: 19 n=8, m=5: 3 n=5, m=3: 4 n=1000000, m=3: 374433

5.4 手动验证递推过程

以 n=5, m=3 为例（编号 0~4）：

最终 survivor = 3，转为 1 编号 =4。验证正确！

六、扩展：出列顺序

如果不仅要求最后幸存者，还要知道每个人的出列顺序，递推公式就不够了，需要模拟。循环链表法可以轻松记录出列顺序：

funcJosephusOrder(n,mint)[]int{ifn<=0||m<=0{returnnil}// 构建循环链表head:=&CLNode{No:1}cur:=headfori:=2;i<=n;i++{cur.Next=&CLNode{No:i}cur=cur.Next}cur.Next=head prev:=headforprev.Next!=head{prev=prev.Next}varorder[]intforcur.Next!=cur{fori:=1;i<m;i++{prev=cur cur=cur.Next}order=append(order,cur.No)prev.Next=cur.Next cur=cur.Next}order=append(order,cur.No)// 最后幸存者returnorder}