据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
----------------------------------------josephus.go------------------------------------------
package josephus
import (
"container/ring"
"fmt"
)
type Player struct {
pos int
alive bool
}
type Josephus struct {
ring *ring.Ring
count int
counter int
startPos int
orderToDie int
remain int
}
func New(count, orderToDie int) *Josephus {
r := ring.New(count)
for i := 1; i < count+1; i++ {
r.Value = &Player{i, true}
r = r.Next()
}
return &Josephus{
ring: r,
count: count,
remain: count,
counter: 0,
startPos: 1,
orderToDie: orderToDie,
}
}
// Show()方法展示死亡过程,并进行标记,不从结构中移除
func (this *Josephus) Show() {
for i := 1; this.remain > this.orderToDie; i++ {
fmt.Printf("\n开始第%d轮,共%d人\n", i, this.remain)
this.ring.Do(func(item interface{}) {
player := item.(*Player)
if player.alive {
this.counter++
}
if this.counter == this.orderToDie {
player.alive = false
this.counter = 0
this.remain--
fmt.Printf("player %d died \n", player.pos)
}
})
}
}
func (this *Josephus) ShowRemain() {
fmt.Println()
this.ring.Do(func(item interface{}) {
player := item.(*Player)
if player.alive {
fmt.Printf("存活 %v\n", item)
}
})
}
// Run()方法将死亡玩家和存活玩家拆分并返回
func (this *Josephus ) Run() (dead,lived *ring.Ring) {
r:=this.ring
for ; this.remain >= this.orderToDie; r=r.Next() {
player := r.Value.(*Player)
if player.alive {
this.counter++
}
if this.counter == this.orderToDie {
player.alive = false
this.counter = 0
this.remain--
r=r.Prev()
deadPlayer:=r.Unlink(1)
// 注意Ring的New方法创建的对象至少有一个元素,为避免这个多余的空元素,直接指定
if dead==nil{
dead=deadPlayer
}else{
dead.Link(deadPlayer)
}
dead.Link(deadPlayer)
}
}
lived=r
return
}
-------------------------------josephus_test.go-----------------------------------------------
package josephus
import (
"testing"
"fmt"
)
func TestJosephus(t *testing.T) {
j:=New(41,3)
j.Show()
j.ShowRemain()
fmt.Println("----------------------------------")
j2:=New(41,3)
dead,lived:=j2.Run()
fmt.Println("存活")
lived.Do(func(item interface{}) {
fmt.Printf("%d,",item.(*Player).pos)
})
fmt.Println("\n死亡")
dead.Do(func(item interface{}) {
fmt.Printf("%d,",item.(*Player).pos)
})
}