如何用golang實(shí)現(xiàn)約瑟夫環(huán)

約瑟夫環(huán)概念：

約瑟夫環(huán)是一個(gè)數(shù)學(xué)的應(yīng)用問(wèn)題：已知n個(gè)人（以編號(hào)1，2，3...n分別表示）圍坐在一張圓桌周?chē)?。從編?hào)為k的人開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列；依此規(guī)律重復(fù)下去，直到圓桌周?chē)娜巳砍隽?。通常解決這類(lèi)問(wèn)題時(shí)把編號(hào)從0~n-1，最后結(jié)果+1即為原問(wèn)題的解。

特點(diǎn)：

1、第一個(gè)節(jié)點(diǎn)稱(chēng)為頭部節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)稱(chēng)為尾部節(jié)點(diǎn)

2、每個(gè)節(jié)點(diǎn)都單方面的指向下一個(gè)節(jié)點(diǎn)

3、尾部節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)指向頭部節(jié)點(diǎn)

題目：

17世紀(jì)的法國(guó)數(shù)學(xué)家加斯帕講了這樣一個(gè)故事： 15個(gè)教徒和15 個(gè)非教徒，在深海?上遇險(xiǎn)，必須將一半的人投入海?中，其余的人才能幸免于難，于是想了一個(gè)辦法： 30個(gè)人圍成一圓圈，從第一個(gè)人開(kāi)始依次報(bào)數(shù)，每數(shù)到第九個(gè)人就將他扔入大海?，如此循環(huán)進(jìn)行直到僅余15個(gè)人為止。問(wèn)怎樣排法，才能使每次投入大海?的都是非教徒。

這就是典型的約瑟夫環(huán)問(wèn)題，可以用單向鏈表環(huán)解決，具體代碼如下：

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,
	}
}

// 獲取頭部節(jié)點(diǎn)
func (sl *SingleLink)GetHead()*LinkNode{
	return  sl.head
}

// 獲取尾部節(jié)點(diǎn)
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
		}
	}
}

//鏈表長(zhǎng)度
func (sl *SingleLink) Length() int{
	return sl.size
}

//插入數(shù)據(jù)（頭插）
func (sl *SingleLink) InsertByHead(node *LinkNode){
	if node == nil{
		return
	}
	// 判斷是否第一個(gè)節(jié)點(diǎn)
	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++
}

//插入數(shù)據(jù)（尾插）
func (sl *SingleLink) InsertByTail(node *LinkNode) {
	if node == nil{
		return
	}
	// 插入第一個(gè)節(jié)點(diǎn)
	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 ++
}

//插入數(shù)據(jù)（下標(biāo)）位置
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(){
			//往尾部添加節(jié)點(diǎn)
			sl.InsertByTail(node)
		}else{
			preNode := sl.Search(index-1)     // 下標(biāo)為 index 的上一個(gè)節(jié)點(diǎn)
			currentNode := sl.Search(index)		// 下標(biāo)為 index 的節(jié)點(diǎn)
			preNode.Next = node
			node.Next = currentNode
			sl.size++
		}
	}
}

//刪除數(shù)據(jù)（下標(biāo)）位置
func (sl *SingleLink) DeleteByIndex(index int) {
	if sl.Length() == 0 || index > sl.Length(){
		return
	}
	// 刪除第一個(gè)節(jié)點(diǎn)
	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--
}

// 查詢(xún)數(shù)據(jù)
func (sl *SingleLink) Search(index int)(node *LinkNode)  {
	if 	sl.Length() == 0 || index > sl.Length(){
		return nil
	}
	// 是否頭部節(jié)點(diǎn)
	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個(gè)元素的環(huán)
	for i:=0;i<30;i++{
		snode := &LinkNode{
			Data:i,
		}
		sl.InsertByIndex(i,snode)
	}

	//循環(huán)淘汰第9個(gè)元素
	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()
}

執(zhí)行結(jié)果

================ 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