go 环形单向链表实现约瑟夫问题

清疚 2021-07-24 12:28 418阅读 0赞

# 一 Josephu 问题 #

Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

# 二 分析 #

用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

# 三 图解 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 四 代码 #

package main
    
    import (
       "fmt"
    )
    
    // 小孩结构体
    type Boy struct {
       No   int  // 编号
       Next *Boy // 指向下一个小孩的指针，默认值是 nil。
    }
    
    // 编写一个函数，构成单向的环形链表
    // num ：表示小孩的个数。
    // *Boy ：返回该环形的链表的第一个小孩的指针。
    func AddBoy(num int) *Boy {
       first := &Boy{}  // 空结点
       curBoy := &Boy{} // 空结点
       // 判断
       if num < 1 {
          fmt.Println("num的值不对")
          return first
       }
       // 循环的构建这个环形链表
       for i := 1; i <= num; i++ {
          boy := &Boy{
             No: i,
          }
          // 构成循环链表，需要一个辅助指针
          // 第一个小孩特殊处理
          if i == 1 { // 第一个小孩
             first = boy // fisrt 不动
             curBoy = boy
             curBoy.Next = first //
          } else {
             curBoy.Next = boy
             curBoy = boy
             curBoy.Next = first // 构造环形链表
          }
       }
       return first
    }
    
    // 显示单向的环形链表：遍历
    func ShowBoy(first *Boy) {
       // 环形链表为空的情况
       if first.Next == nil {
          fmt.Println("链表为空，没有小孩...")
          return
       }
       // 创建一个指针，帮助遍历，走到这里，说明至少有一个小孩
       curBoy := first
       for {
          fmt.Printf("小孩编号=%d ->", curBoy.No)
          // 退出的条件
          if curBoy.Next == first {
             break
          }
          // curBoy 移动到下一个位置
          curBoy = curBoy.Next
       }
    }
    
    // 出圈
    func PlayGame(first *Boy, startNo int, countNum int) {
       // 1 空的链表单独的处理
       if first.Next == nil {
          fmt.Println("空的链表，没有小孩")
          return
       }
       // 2 辅助指针，帮助我们删除小孩
       tail := first
       // 3 让 tail 定位到环形链表的最后一个小孩，因为 tail 在删除小孩时需要使用到。
       for {
          if tail.Next == first { // 说明 tail 到了最后的小孩
             break
          }
          tail = tail.Next
       }
       // 4 让 first 移动到 startNo 位置，tail 紧随其后
       for i := 1; i <= startNo-1; i++ {
          first = first.Next
          tail = tail.Next
       }
       fmt.Println()
       // 5 开始数 countNum, 然后就删除 first 指向的小孩
       for {
          // 开始数 countNum-1 次
          for i := 1; i <= countNum-1; i++ {
             first = first.Next
             tail = tail.Next
          }
          fmt.Printf("小孩编号为%d 出圈 \n", first.No)
          // 删除 first 指向的小孩
          first = first.Next
          tail.Next = first
          // 如果 tail == first, 圈子中只有一个小孩.
          if tail == first {
             break
          }
       }
       fmt.Printf("小孩编号为%d 出圈 \n", first.No)
    }
    
    func main() {
       first := AddBoy(30)
       // 显示
       ShowBoy(first)
       PlayGame(first, 20, 8)
    }

# 五 测试 #

小孩编号=1 ->小孩编号=2 ->小孩编号=3 ->小孩编号=4 ->小孩编号=5 ->小孩编号=6 ->小孩编号=7 ->小孩编号=8 ->小孩编号=9 ->小孩编号=10 ->小孩编号=11 ->小孩编号=12 ->小孩编号=13 ->小孩编号=14 ->小孩编号=15 ->小孩编号=16 ->小孩编号=17 ->小孩编号=18 ->小孩编号=19 ->小孩编号=20 ->小孩编号=21 ->小孩编号=22 ->小孩编号=23 ->小孩编号=24 ->小孩编号=25 ->小孩编号=26 ->小孩编号=27 ->小孩编号=28 ->小孩编号=29 ->小孩编号=30 ->
    小孩编号为27 出圈
    小孩编号为5 出圈
    小孩编号为13 出圈
    小孩编号为21 出圈
    小孩编号为30 出圈
    小孩编号为9 出圈
    小孩编号为18 出圈
    小孩编号为28 出圈
    小孩编号为8 出圈
    小孩编号为19 出圈
    小孩编号为1 出圈
    小孩编号为12 出圈
    小孩编号为24 出圈
    小孩编号为7 出圈
    小孩编号为22 出圈
    小孩编号为6 出圈
    小孩编号为23 出圈
    小孩编号为11 出圈
    小孩编号为29 出圈
    小孩编号为17 出圈
    小孩编号为14 出圈
    小孩编号为4 出圈
    小孩编号为3 出圈
    小孩编号为10 出圈
    小孩编号为16 出圈
    小孩编号为26 出圈
    小孩编号为25 出圈
    小孩编号为15 出圈
    小孩编号为2 出圈
    小孩编号为20 出圈

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/cf3d7f7d7c9b46b09bcadaa4dcda37a0.png