如何用golang实现约瑟夫环

2025-02-04 技术教程

约瑟夫环概念：

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时把编号从0~n-1，最后结果+1即为原问题的解。

特点：

1、第一个节点称为头部节点，最后一个节点称为尾部节点

2、每个节点都单方面的指向下一个节点

3、尾部节点下一个节点指向头部节点

题目：

17世纪的法国数学家加斯帕讲了这样一个故事： 15个教徒和15 个非教徒，在深海海上遇险，必须将一半的人投入海海中，其余的人才能幸免于难，于是想了一个办法： 30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海海的都是非教徒。

这就是典型的约瑟夫环问题，可以用单向链表环解决，具体代码如下：

packagemainimport"fmt"typeLinkNodestruct{Datainterface{}Next*LinkNode}typeSingleLinkstruct{head*LinkNodetail*LinkNodesizeint}//初始化链表funcInitSingleLink()(*SingleLink){return&SingleLink{head:nil,tail:nil,size:0,}}//获取头部节点func(sl*SingleLink)GetHead()*LinkNode{returnsl.head}//获取尾部节点func(sl*SingleLink)GetTail()*LinkNode{returnsl.tail}//打印链表func(sl*SingleLink)Print(){fmt.Println("SingleLinksize:",sl.Length())ifsl.size==0{return}ptr:=sl.GetHead()headNode:=sl.GetHead()forptr!=nil{fmt.Println("Data:",ptr.Data)ptr=ptr.Nextifptr.Next==headNode{fmt.Println("Data:",ptr.Data)break}}}//链表长度func(sl*SingleLink)Length()int{returnsl.size}//插入数据（头插）func(sl*SingleLink)InsertByHead(node*LinkNode){ifnode==nil{return}//判断是否第一个节点ifsl.Length()==0{sl.head=nodesl.tail=nodenode.Next=nil}else{oldHeadNode:=sl.GetHead()sl.head=nodesl.tail.Next=nodesl.head.Next=oldHeadNode}sl.size++}//插入数据（尾插）func(sl*SingleLink)InsertByTail(node*LinkNode){ifnode==nil{return}//插入第一个节点ifsl.size==0{sl.head=nodesl.tail=nodenode.Next=nil}else{sl.tail.Next=nodenode.Next=sl.headsl.tail=node}sl.size++}//插入数据（下标）位置func(sl*SingleLink)InsertByIndex(indexint,node*LinkNode){ifnode==nil{return}//往头部插入ifindex==0{sl.InsertByHead(node)}else{ifindex>sl.Length(){return}elseifindex==sl.Length(){//往尾部添加节点sl.InsertByTail(node)}else{preNode:=sl.Search(index-1)//下标为index的上一个节点currentNode:=sl.Search(index)//下标为index的节点preNode.Next=nodenode.Next=currentNodesl.size++}}}//删除数据（下标）位置func(sl*SingleLink)DeleteByIndex(indexint){ifsl.Length()==0||index>sl.Length(){return}//删除第一个节点ifindex==0{sl.head=sl.head.Nextsl.tail.Next=sl.head}else{preNode:=sl.Search(index-1)ifindex!=sl.Length()-1{nextNode:=sl.Search(index).NextpreNode.Next=nextNode}else{sl.tail=preNodepreNode.Next=sl.head}}sl.size--}//查询数据func(sl*SingleLink)Search(indexint)(node*LinkNode){ifsl.Length()==0||index>sl.Length(){returnnil}//是否头部节点ifindex==0{returnsl.GetHead()}node=sl.headfori:=0;i<=index;i++{node=node.Next}return}func(sl*SingleLink)pop(){popIndex:=8delNode:=sl.Search(popIndex)fmt.Println("POPnode:",delNode.Data)sl.DeleteByIndex(popIndex)sl.tail=sl.Search(popIndex-1)sl.head=sl.Search(popIndex)fmt.Printf("Head:%v,Tail:%v\n",sl.head.Data,sl.tail.Data)}funcmain(){//初始化链表sl:=InitSingleLink()//生成30个元素的环fori:=0;i<30;i++{snode:=&LinkNode{Data:i,}sl.InsertByIndex(i,snode)}//循环淘汰第9个元素varroundintforsl.size>15{fmt.Printf("================Round%d================\n",round)sl.pop()round++}//获胜者fmt.Println("================Finish================")fmt.Println("Peoplewhosurvived.")sl.Print()}

执行结果

================Round0================POPnode:9Head:10,Tail:8================Round1================POPnode:19Head:20,Tail:18================Round2================POPnode:29Head:0,Tail:28================Round3================POPnode:10Head:11,Tail:8================Round4================POPnode:21Head:22,Tail:20================Round5================POPnode:2Head:3,Tail:1================Round6================POPnode:14Head:15,Tail:13================Round7================POPnode:26Head:27,Tail:25================Round8================POPnode:8Head:11,Tail:7================Round9================POPnode:23Head:24,Tail:22================Round10================POPnode:6Head:7,Tail:5================Round11================POPnode:22Head:24,Tail:20================Round12================POPnode:7Head:11,Tail:5================Round13================POPnode:25Head:27,Tail:24================Round14================POPnode:13Head:15,Tail:12================Finish================Peoplewhosurvived.SingleLinksize:15Data:15Data:16Data:17Data:18Data:20Data:24Data:27Data:28Data:0Data:1Data:3Data:4Data:5Data:11Data:12