約瑟夫環概念：

創新互聯公司專注于臨澧企業網站建設,自適應網站建設,商城建設。臨澧網站建設公司,為臨澧等地區提供建站服務。全流程按需策劃，專業設計，全程項目跟蹤，創新互聯公司專業和態度為您提供的服務

約瑟夫環是一個數學的應用問題：已知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://www.xueling.net.cn/article/dhshcj.html