自己动手用Golang实现约瑟夫环算法的示例
作者:筑梦攻城狮 发布时间:2024-04-23 09:48:50
继上一篇单向链表,单线链表可以进一步扩展为环,如下图所示:
特点:
1、第一个节点称为头部节点,最后一个节点称为尾部节点
2、每个节点都单方面的指向下一个节点
3、尾部节点下一个节点指向头部节点
题目:
17世纪的法国数学家加斯帕讲了这样一个故事: 15个教徒和15 个非教徒,在深海海上遇险,必须将一半的人投入海海中,其余的人才能幸免于难,于是想了一个办法: 30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海海的都是非教徒。
这就是典型的约瑟夫环问题,可以用单向链表环解决,具体代码如下:
package main
import "fmt"
type LinkNode struct {
Data interface{}
Next *LinkNode
}
type SingleLink struct {
head *LinkNode
tail *LinkNode
size int
}
// 初始化链表
func InitSingleLink()(*SingleLink){
return &SingleLink{
head:nil,
tail:nil,
size:0,
}
}
// 获取头部节点
func (sl *SingleLink)GetHead()*LinkNode{
return sl.head
}
// 获取尾部节点
func (sl *SingleLink)GetTail()*LinkNode{
return sl.tail
}
// 打印链表
func (sl *SingleLink) Print(){
fmt.Println("SingleLink size:",sl.Length())
if sl.size == 0{
return
}
ptr := sl.GetHead()
headNode := sl.GetHead()
for ptr != nil{
fmt.Println("Data:",ptr.Data)
ptr = ptr.Next
if ptr.Next == headNode{
fmt.Println("Data:",ptr.Data)
break
}
}
}
//链表长度
func (sl *SingleLink) Length() int{
return sl.size
}
//插入数据(头插)
func (sl *SingleLink) InsertByHead(node *LinkNode){
if node == nil{
return
}
// 判断是否第一个节点
if sl.Length() == 0{
sl.head = node
sl.tail = node
node.Next = nil
}else{
oldHeadNode := sl.GetHead()
sl.head = node
sl.tail.Next = node
sl.head.Next = oldHeadNode
}
sl.size++
}
//插入数据(尾插)
func (sl *SingleLink) InsertByTail(node *LinkNode) {
if node == nil{
return
}
// 插入第一个节点
if sl.size == 0{
sl.head = node
sl.tail = node
node.Next = nil
}else{
sl.tail.Next = node
node.Next = sl.head
sl.tail = node
}
sl.size ++
}
//插入数据(下标)位置
func (sl *SingleLink) InsertByIndex(index int, node *LinkNode){
if node == nil{
return
}
// 往头部插入
if index == 0 {
sl.InsertByHead(node)
}else{
if index > sl.Length(){
return
}else if index == sl.Length(){
//往尾部添加节点
sl.InsertByTail(node)
}else{
preNode := sl.Search(index-1) // 下标为 index 的上一个节点
currentNode := sl.Search(index) // 下标为 index 的节点
preNode.Next = node
node.Next = currentNode
sl.size++
}
}
}
//删除数据(下标)位置
func (sl *SingleLink) DeleteByIndex(index int) {
if sl.Length() == 0 || index > sl.Length(){
return
}
// 删除第一个节点
if index == 0{
sl.head = sl.head.Next
sl.tail.Next = sl.head
}else{
preNode := sl.Search(index-1)
if index != sl.Length()-1{
nextNode := sl.Search(index).Next
preNode.Next = nextNode
}else{
sl.tail = preNode
preNode.Next = sl.head
}
}
sl.size--
}
// 查询数据
func (sl *SingleLink) Search(index int)(node *LinkNode) {
if sl.Length() == 0 || index > sl.Length(){
return nil
}
// 是否头部节点
if index == 0{
return sl.GetHead()
}
node = sl.head
for i:=0;i<=index;i++{
node = node.Next
}
return
}
func (sl *SingleLink)pop(){
popIndex := 8
delNode := sl.Search(popIndex)
fmt.Println("POP node : ",delNode.Data)
sl.DeleteByIndex(popIndex)
sl.tail = sl.Search(popIndex - 1)
sl.head = sl.Search(popIndex)
fmt.Printf("Head:%v , Tail:%v\n",sl.head.Data,sl.tail.Data)
}
func main() {
// 初始化链表
sl := InitSingleLink()
// 生成30个元素的环
for i:=0;i<30;i++{
snode := &LinkNode{
Data:i,
}
sl.InsertByIndex(i,snode)
}
//循环淘汰第9个元素
var round int
for sl.size > 15{
fmt.Printf("================ Round %d ================\n",round)
sl.pop()
round ++
}
// 获胜者
fmt.Println("================ Finish ================")
fmt.Println("People who survived.")
sl.Print()
}
执行结果
================ Round 0 ================
POP node : 9
Head:10 , Tail:8
================ Round 1 ================
POP node : 19
Head:20 , Tail:18
================ Round 2 ================
POP node : 29
Head:0 , Tail:28
================ Round 3 ================
POP node : 10
Head:11 , Tail:8
================ Round 4 ================
POP node : 21
Head:22 , Tail:20
================ Round 5 ================
POP node : 2
Head:3 , Tail:1
================ Round 6 ================
POP node : 14
Head:15 , Tail:13
================ Round 7 ================
POP node : 26
Head:27 , Tail:25
================ Round 8 ================
POP node : 8
Head:11 , Tail:7
================ Round 9 ================
POP node : 23
Head:24 , Tail:22
================ Round 10 ================
POP node : 6
Head:7 , Tail:5
================ Round 11 ================
POP node : 22
Head:24 , Tail:20
================ Round 12 ================
POP node : 7
Head:11 , Tail:5
================ Round 13 ================
POP node : 25
Head:27 , Tail:24
================ Round 14 ================
POP node : 13
Head:15 , Tail:12
================ Finish ================
People who survived.
SingleLink size: 15
Data: 15
Data: 16
Data: 17
Data: 18
Data: 20
Data: 24
Data: 27
Data: 28
Data: 0
Data: 1
Data: 3
Data: 4
Data: 5
Data: 11
Data: 12
来源:https://blog.51cto.com/pmghong/2462943
猜你喜欢
- 方法超级简单,把时间格式化一下就好了,直接奉上代码function transDate() { var $time
- 问题:如何经过convTransposed1d输出指定大小的特征?import torchfrom torch import nnimpor
- 本文讲述了python在Windows下安装setuptools(easy_install工具)的方法。分享给大家供大家参考,具体如下:【题
- 这篇文章主要介绍了如何基于python操作json文件获取内容,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,
- 周末在家,儿子闹着要玩游戏,让玩吧,不利于健康,不让玩吧,扛不住他折腾,于是想,不如一起搞个小游戏玩玩!之前给他编过猜数字 和 掷骰子 游戏
- 首先这里声明一下,关于我测试浏览器的版本是chrome15.0.874.121 Firefox 8.01 IE9 IETester下面的代码
- 本文以简单示例分析了python中关键字is与 ==的区别,供大家参考一下。首先说明一下Python学习中几个相关的小知识点。Python中
- 一、base64模块base64模块提供了在二进制数据和可打印ASCII字符间编解码的功能,包括 RFC3548中定义的Base16, Ba
- <% a="福建是中国的一个省|我们美丽中国的武夷山!" b="中国,我们,武夷山,福建,美国,苹果&q
- 多线程-共享全局变量#coding=utf-8from threading import Threadimport timeg_num =
- 理解切片基本用法:首先需要明白,可迭代对象,按照正数索引(正序)是从0开始的,按照负数索引(逆序)是从-1开始的。>>>
- 背景:今天同事写代码,用python读取一个四五百兆的文件,然后做一串逻辑上很直观的处理。结果处理了一天还没有出来结果。问题出在哪里呢?解决
- 观看本文前最好有一定的Linux命令基础,具体为centos7.3环境中清除使用yum安装的Mysql卸载前请先关闭Mysql服务servi
- JetBrains针对学生推出了免费使用资格,但是很多同学却不知道或者说不知道怎样获得免费资格,只能千辛万苦的去寻找破解密钥,但现在JetB
- 前言当我们在用python时可能会遇到想要把txt文档里的数据读取出来然后进行绘图,那么我们要怎么才能够将txt里的数据读取出来呢?假设有t
- 有表如下:如何获得如下结果:解法使用xml转换代码如下: CREATE TABLE body (
- 转发和重定向:转发:一次请求和响应,请求的地址没有发生变化,如果此时刷新页面,就会出现重做现象。重定向:一次以上的请求和响应,请求地址发生一
- 本文实例讲述了Python打印scrapy蜘蛛抓取树结构的方法。分享给大家供大家参考。具体如下:通过下面这段代码可以一目了然的知道scrap
- <%'解析一个xml文件的公用函数集合dim document'装载一个xml文档,函数名Loaddocument(文
- 在很多企业会使用闲置的 Windows 机器作为临时服务器,有时候我们想远程调用里面的程序或查看日志文件Windows 内置的服务