41.Go语言·数据结构·环形单向链表·约瑟夫问题[丢手绢问题]

main.go

// 约瑟夫————环形链表应用
package main

import (
    "fmt"
)

type Boy struct {
    No int
    Next *Boy  //默认值nil
}


// 编写一个函数，构成单向的环形链表
// num：表示小孩的个数
// *Boy:返回该环形链表的第一个小孩指针
func Join(num int) *Boy {
    first    := &Boy{}
    currtBoy := &Boy{}

    if num<1 {
        fmt.Println("参数不对~~~")
        return first
    }

    for i := 1; i <=num; i++ {
        boy := &Boy{
            No:i,
        }
        // 构成循环链表，需要一个复制指针[帮忙的]
        if i == 1 {
            first  = boy
            currtBoy = boy
            currtBoy.Next = first
        }else{
            currtBoy.Next = boy
            currtBoy = boy
            currtBoy.Next = first
        }
    }
    return first
}

// 显示
func Show (first *Boy) {
    fmt.Println()
    if first.Next == nil {
        return 
    }
    currBoy := first
    for {
        fmt.Printf("[No.%d]-->",currBoy.No)
        if currBoy.Next == first {
            fmt.Printf("[No.%d]",first.No)
            break
        }
        currBoy = currBoy.Next
    }
    fmt.Println()
}


/*
   设置编号为1，2，3，...，n的n个人围坐一圈，约定编号为k（1<=k<=n）
的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，
数到m的那个人又出列，以此类推，直到所有人出列为止，由此产生一个出列编号的
序列
 */
func PlayGame(first *Boy ,startNo int,countNum int) {

    if first.Next == nil {
        fmt.Println("没人玩~~~")
        return 
    }

    //定义一个临时变量，找到环形的最后的节点
    //tail指向最后一个小孩
    tail := first
    for {
        if tail.Next == first{
            break
        }
        tail = tail.Next
    }


    fmt.Println()
    // 4.约定编号为k（1<=k<=n）
    // 让first移动到 startNo，不能超过人数n
    // 即是，我们从 约定编号为k(startNo)的人开始数
    for i := 1; i <=startNo-1; i++ {
        first = first.Next
        tail  = tail .Next
    }

    
    // 5.从1开始报数，数到m的那个人出列，
    // 它的下一位又从1开始报数，数到m的那个人又出列
    // 从1开始报数，数到m[countNum]
    for {
        // 从1开始报数，数到countNum-1
        for i := 1; i <=countNum-1; i++ {
            first = first.Next
            tail  = tail .Next
        }


        fmt.Printf("[No.%d 出圈啦！] \n",first.No)
        first = first.Next
        tail.Next = first

        if tail == first {
            break
        }
    }
    fmt.Printf("[No.%d 最后一个出圈啦！] \n",first.No)
}


func main() {
    // 1.设置编号为1，2，3，...，n的n个人围坐一圈
    first := Join(5)
    // 2.大家整齐站好咯。
    Show(first)
    // 3.开始玩游戏咯
    PlayGame(first,2,3)
}