如何用golang实现约瑟夫环-创新互联
约瑟夫环概念：
创新互联公司专注于临澧企业网站建设,自适应网站建设,商城建设。临澧网站建设公司,为临澧等地区提供建站服务。全流程按需策划，专业设计，全程项目跟踪，创新互联公司专业和态度为您提供的服务约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时把编号从0~n-1，最后结果+1即为原问题的解。
特点：
1、第一个节点称为头部节点，最后一个节点称为尾部节点
2、每个节点都单方面的指向下一个节点
3、尾部节点下一个节点指向头部节点
题目：
17世纪的法国数学家加斯帕讲了这样一个故事： 15个教徒和15 个非教徒，在深海海上遇险，必须将一半的人投入海海中，其余的人才能幸免于难，于是想了一个办法： 30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海海的都是非教徒。
这就是典型的约瑟夫环问题，可以用单向链表环解决，具体代码如下：
package main import "fmt" type LinkNode struct { Data interface{} Next *LinkNode } type SingleLink struct { head *LinkNode tail *LinkNode size int } // 初始化链表 func InitSingleLink()(*SingleLink){ return &SingleLink{ head:nil, tail:nil, size:0, } } // 获取头部节点 func (sl *SingleLink)GetHead()*LinkNode{ return sl.head } // 获取尾部节点 func (sl *SingleLink)GetTail()*LinkNode{ return sl.tail } // 打印链表 func (sl *SingleLink) Print(){ fmt.Println("SingleLink size:",sl.Length()) if sl.size == 0{ return } ptr := sl.GetHead() headNode := sl.GetHead() for ptr != nil{ fmt.Println("Data:",ptr.Data) ptr = ptr.Next if ptr.Next == headNode{ fmt.Println("Data:",ptr.Data) break } } } //链表长度 func (sl *SingleLink) Length() int{ return sl.size } //插入数据（头插） func (sl *SingleLink) InsertByHead(node *LinkNode){ if node == nil{ return } // 判断是否第一个节点 if sl.Length() == 0{ sl.head = node sl.tail = node node.Next = nil }else{ oldHeadNode := sl.GetHead() sl.head = node sl.tail.Next = node sl.head.Next = oldHeadNode } sl.size++ } //插入数据（尾插） func (sl *SingleLink) InsertByTail(node *LinkNode) { if node == nil{ return } // 插入第一个节点 if sl.size == 0{ sl.head = node sl.tail = node node.Next = nil }else{ sl.tail.Next = node node.Next = sl.head sl.tail = node } sl.size ++ } //插入数据（下标）位置 func (sl *SingleLink) InsertByIndex(index int, node *LinkNode){ if node == nil{ return } // 往头部插入 if index == 0 { sl.InsertByHead(node) }else{ if index > sl.Length(){ return }else if index == sl.Length(){ //往尾部添加节点 sl.InsertByTail(node) }else{ preNode := sl.Search(index-1) // 下标为 index 的上一个节点 currentNode := sl.Search(index) // 下标为 index 的节点 preNode.Next = node node.Next = currentNode sl.size++ } } } //删除数据（下标）位置 func (sl *SingleLink) DeleteByIndex(index int) { if sl.Length() == 0 || index > sl.Length(){ return } // 删除第一个节点 if index == 0{ sl.head = sl.head.Next sl.tail.Next = sl.head }else{ preNode := sl.Search(index-1) if index != sl.Length()-1{ nextNode := sl.Search(index).Next preNode.Next = nextNode }else{ sl.tail = preNode preNode.Next = sl.head } } sl.size-- } // 查询数据 func (sl *SingleLink) Search(index int)(node *LinkNode) { if sl.Length() == 0 || index > sl.Length(){ return nil } // 是否头部节点 if index == 0{ return sl.GetHead() } node = sl.head for i:=0;i<=index;i++{ node = node.Next } return } func (sl *SingleLink)pop(){ popIndex := 8 delNode := sl.Search(popIndex) fmt.Println("POP node : ",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) } func main() { // 初始化链表 sl := InitSingleLink() // 生成30个元素的环 for i:=0;i<30;i++{ snode := &LinkNode{ Data:i, } sl.InsertByIndex(i,snode) } //循环淘汰第9个元素 var round int for sl.size > 15{ fmt.Printf("================ Round %d ================\n",round) sl.pop() round ++ } // 获胜者 fmt.Println("================ Finish ================") fmt.Println("People who survived.") sl.Print() }执行结果
================ Round 0 ================ POP node : 9 Head:10 , Tail:8 ================ Round 1 ================ POP node : 19 Head:20 , Tail:18 ================ Round 2 ================ POP node : 29 Head:0 , Tail:28 ================ Round 3 ================ POP node : 10 Head:11 , Tail:8 ================ Round 4 ================ POP node : 21 Head:22 , Tail:20 ================ Round 5 ================ POP node : 2 Head:3 , Tail:1 ================ Round 6 ================ POP node : 14 Head:15 , Tail:13 ================ Round 7 ================ POP node : 26 Head:27 , Tail:25 ================ Round 8 ================ POP node : 8 Head:11 , Tail:7 ================ Round 9 ================ POP node : 23 Head:24 , Tail:22 ================ Round 10 ================ POP node : 6 Head:7 , Tail:5 ================ Round 11 ================ POP node : 22 Head:24 , Tail:20 ================ Round 12 ================ POP node : 7 Head:11 , Tail:5 ================ Round 13 ================ POP node : 25 Head:27 , Tail:24 ================ Round 14 ================ POP node : 13 Head:15 , Tail:12 ================ Finish ================ People who survived. SingleLink size: 15 Data: 15 Data: 16 Data: 17 Data: 18 Data: 20 Data: 24 Data: 27 Data: 28 Data: 0 Data: 1 Data: 3 Data: 4 Data: 5 Data: 11 Data: 12另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
标题名称：如何用golang实现约瑟夫环-创新互联
本文链接：http://6mz.cn/article/dhshcj.html