Golang 链表实现约瑟夫算法

Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式：41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是一开始要站在什么地方才能避免自杀？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
——摘自约瑟夫问题_百度百科

package main

import (
    "fmt"
    "os"
)
func main() {
    traverse(initLinkedList(13))
}

type Node struct {
   data int   next *Node}
/** 初始化链表 */
func initLinkedList(num int) *Node  {
   if num < 0 {
      os.Exit(-1)
   }

   p := new(Node)
   p.data = 1   //临时存储链表第一元素   qTemp := p
   for i := 0; i < num ; i++  {
      temp := new(Node)
      temp.data = i
      p.next = temp
      p = temp
   }
   //形成环形链表   p.next = qTemp
   return p
}

/**   判断链表是否为空 */
func isEmpty(list *Node) bool {

   //链表是环行 初始化链表最后指向自己  initLinkedList 
  if list.next == list {
      return true   }
   return false}


/**   链表遍历 */
   func traverse(list *Node)  {
   if isEmpty(list) {
      return   }

   p := list.next
   for ;p != list ; p = p.next  {
      fmt.Printf("%d",p.data)
   }
   fmt.Printf("%d\n",list.data)

}

/**   计算链表长度 */
func listLength(list *Node) int  {
   i := 1   //判断当前节点不等于自己 继续循环  
  for p := list.next; p!=list ;  p = p.next  {
      i++
   }
   return i
}

/**   约瑟夫实现 */
func jose(list *Node,num int)  {

   p := list.next
   count := 1   for listLength(list) > 1 {
      //循环符合删除数据      for i := 1; i < num - 1; i++  {
          p = p.next
      }
      //下面是删除节点      temp := p.next
      fmt.Printf("第%d个出局的人为: %3d号",count,temp.data)
      p.next = temp.next
      p = temp.next
      temp = nil      count++
   }
   fmt.Println("最后获胜是的:",p.data)
}

参考链接 https://blog.csdn.net/tangguangqiang/article/details/53914838

有疑问加站长微信联系（非本文作者）