GoFrame gring-基本使用

約瑟夫問題

我們使用?ring?來模擬一下約瑟夫問題：

著名猶太歷史學家 Josephus有過以下的故事：在羅馬人占領喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人。接著，再越過k-1個人，并殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續(xù)活著。問題是，給定了和，一開始要站在什么地方才能避免被處決？

以下示例為非并發(fā)安全場景。

package main

import (
    "fmt"
    "github.com/gogf/gf/v2/container/gring"
)

type Player struct {
    position int  // 位置
    alive    bool // 是否存活
}

const (
    playerCount = 41  // 玩家人數
    startPos    = 1   // 開始報數位置
)

var (
    deadline = 3
)

func main() {
    r := gring.New(playerCount)

    // 設置所有玩家初始值
    for i := 1; i <= playerCount; i++ {
        r.Put(&Player{i, true})
    }

    // 如果開始報數的位置不為1，則設置開始位置
    if startPos > 1 {
        r.Move(startPos - 1)
    }

    counter   := 1  // 報數從1開始，因為下面的循環(huán)從第二個開始計算
    deadCount := 0  // 死亡人數，初始值為0

    // 直到所有人都死亡，否則循環(huán)一直執(zhí)行
    for deadCount < playerCount {
        // 跳到下一個人
        r.Next()

        // 如果是活著的人，則報數
        if r.Val().(*Player).alive {
            counter++
        }

        // 如果報數為deadline，則此人淘汰出局
        if counter == deadline {
            r.Val().(*Player).alive = false
            fmt.Printf("Player %d died!\n", r.Val().(*Player).position)
            deadCount++
            counter = 0
        }
    }
}

執(zhí)行后，輸出結果為：

Player 3 died!
Player 6 died!
Player 9 died!
Player 12 died!
Player 15 died!
Player 18 died!
Player 21 died!
Player 24 died!
Player 27 died!
Player 30 died!
Player 33 died!
Player 36 died!
Player 39 died!
Player 1 died!
Player 5 died!
Player 10 died!
Player 14 died!
Player 19 died!
Player 23 died!
Player 28 died!
Player 32 died!
Player 37 died!
Player 41 died!
Player 7 died!
Player 13 died!
Player 20 died!
Player 26 died!
Player 34 died!
Player 40 died!
Player 8 died!
Player 17 died!
Player 29 died!
Player 38 died!
Player 11 died!
Player 25 died!
Player 2 died!
Player 22 died!
Player 4 died!
Player 35 died!
Player 16 died!
Player 31 died!

可以看到16和31是最后兩個出隊列的，因此Josephus將他的朋友與自己安排在第16個與第31個位置是安全的。