约瑟夫(Josephu)问题
设编号为1,2,3,...... n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,他的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
代码实现
package main import "fmt" type Person struct { No int Next *Person } // 编写一个函数,形成单项循环链表 // num 表示人的个数 // *Person 返回该循环链表的第一个人的指针 func Add(num int) *Person { first := &Person{} curPerson := &Person{} // 判断num必须为大于 1 的数 if num < 1 { fmt.Println("num 的值不对") return first } // 循环构建环形链表 for i := 1; i <= num; i++ { person := &Person{ No: i, } if i == 1 { // 第一个人需要特殊处理 first = person curPerson = person curPerson.Next = first } else { curPerson.Next = person curPerson = person curPerson.Next = first } } return first } // 显示单项循环链表 func Show(first *Person) { // 判断环形链表为空的情况 if first.Next == nil { fmt.Println("环形链表为空") return } // 创建一个指针,帮助遍历 curPerson := first for { fmt.Printf("编号:%d -->", curPerson.No) // 退出的条件 if curPerson.Next == first { break } curPerson = curPerson.Next } fmt.Println() } // 游戏逻辑编写 func PlayGame(first *Person, startNum int, countNum int) { // 空链表单独处理 if first.Next == nil { fmt.Println("空链表") return } // 判断 startNum <= 人的总数 if startNum > Count(first) { fmt.Println("开始数字必须小于人的总数") return } // 定义辅助指针,帮助我们移出一个人 tail := first // 让tail 移动到循环链表的最后一个人 for { if tail.Next == first { break } tail = tail.Next } // 让first移动到startNo, 后面我们移出一个人,就以first 为准 for i := 1; i <= startNum-1; i++ { first = first.Next tail = tail.Next } fmt.Println() // 开始数 countNum , 然后移出 first 指向的那个人 for { // 开始报数 countNum - 1 次 for i := 1; i <= countNum-1; i++ { first = first.Next tail = tail.Next } fmt.Println("编号为:", first.No) // 移出first指向的那个人 first = first.Next tail.Next = first // 判断 tail == first 则代表圈子中只有一个人 if tail == first { break } } fmt.Println("最后一个人的编号:", first.No) } // 计算人的总数 func Count(first *Person) (total int) { // 判断环形链表为空的情况 if first.Next == nil { fmt.Println("环形链表为空") return total } // 创建一个指针,帮助遍历 curPerson := first for { total++ // 退出的条件 if curPerson.Next == first { break } curPerson = curPerson.Next } return total } func main() { first := Add(5) // 显示 Show(first) PlayGame(first, 2, 3) }
执行结果:
编号:1 -->编号:2 -->编号:3 -->编号:4 -->编号:5 --> 编号为: 4 编号为: 2 编号为: 1 编号为: 3 最后一个人的编号: 5