Golang 约瑟夫问题

约瑟夫（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