Golang 约瑟夫问题

gopher Golang 67 次浏览 没有评论

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

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Go