数据结构与算法之约瑟夫问题
约瑟夫问题介绍:
据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
编程描述:
有N个孩子手拉手围成一圈,从第M个孩子开始报数,报到第K个孩子出队,然后从下一个孩子继续开始报数,问:所有孩子的出队顺序?
如下图:
约瑟夫问题的数据结构引出:
图 1-1:
问:用什么数据结构来处理这个问题比较合适呢?
我们不妨将图1-1稍作处理,如下图1-2:
如果我们将每一个小人看人一个node节点,每一个节点都有一个指针指向下一个节点,我们很容易的就想到一种数据结构便是单向链表,如果我们将该单项链表的尾和首相连,将尾部指向首部便是图1-1了,便很适合解决该约瑟夫问题,于是我们可以使用单向环形链表数据结构来模拟解决该问题。
数据结构的实现
基础类如下:
模拟孩子的类Child:
class Child { private int no; private Child next; public Child(int no) { this.no = no; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public Child getNext() { return next; } public void setNext(Child next) { this.next = next; } }
模拟约瑟夫环的类CircleSingleLinkedList:
class CircleSingleLinkedList { private Child head; public void init(int n) { //todo } public void show() { //todo } public void delete(int no) { //todo } }
CircleSingleLinkedList的方法实现:
- 初始化创建带有N个节点的约瑟夫环:
分析:我们只要做到将上一个节点的next指向下一个节点,最后一个节点的next指向第一个即可
public void init(int n) { Child cur; if (n < 1) { return; } else if (n == 1) { child = new Child(1); child.setNext(child); } else { child = new Child(1); child.setNext(child); cur = child; for (int i = 2; i <= n; i++) { cur = cur.getNext(); Child cd = new Child(i); cur.setNext(cd); cd.setNext(child); } } }
2.打印约瑟夫环:
分析:从头结点遍历每一个节点,当节点的getNext()==head时,便遍历结束了,相当于遍历到了最后一个
public void show() { if (head == null) { return; } if (head.getNext() == head) { System.out.println(head.getNo()); return; } Child cur = head; while (cur.getNext() != head) { System.out.println(cur.getNo()); cur = cur.getNext(); } System.out.println(cur.getNo()); }
3.为约瑟夫环增加一个节点到最后:
分析:从头结点遍历到最后,将最后一个节点的next指向增加的节点,将增加的节点next指向头结点head即可
public void addLast(Child child) { Child cur = head; while (cur.getNext() != head) { if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在!!"); } cur = cur.getNext(); } if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在!!"); } cur.setNext(child); child.setNext(head); }
4.删除一个约瑟夫环的节点:
遍历约瑟夫环,找到待删除节点的上一个节点,将上一个节点的next指向待删除节点的next即可,但是如果是删除的头结点,则需要将头结点的下一个节点指定为头结点
public void delete(int no) { if (head == null) { return; } Child cur = head; while (cur.getNext() != head) { if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); return; } cur = cur.getNext(); } if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); head = cur.getNext(); } }
至此约瑟夫环的数据结构及基础方法如下:
class CircleSingleLinkedList { private Child head; public void init(int n) { Child cur; if (n < 1) { return; } else if (n == 1) { head = new Child(1); head.setNext(head); } else { head = new Child(1); head.setNext(head); cur = head; for (int i = 2; i <= n; i++) { cur = cur.getNext(); Child cd = new Child(i); cur.setNext(cd); cd.setNext(head); } } } public void addLast(Child child) { Child cur = head; while (cur.getNext() != head) { if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在!!"); } cur = cur.getNext(); } if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在!!"); } cur.setNext(child); child.setNext(head); } public void show() { if (head == null) { return; } if (head.getNext() == head) { System.out.println(head.getNo()); return; } Child cur = head; while (cur.getNext() != head) { System.out.println(cur.getNo()); cur = cur.getNext(); } System.out.println(cur.getNo()); } public void delete(int no) { if (head == null) { return; } Child cur = head; while (cur.getNext() != head) { if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); return; } cur = cur.getNext(); } if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); head = cur.getNext(); } } }
在约瑟夫环数据结构上解决约瑟夫问题
我们从beginNo个孩子开始报数,每一次报readNum个数,则如何进行出队呢?
分析:从第beginNo个孩子作为游戏的开始,就相当于移动约瑟夫环的头结点,将第beginNo个节点作为头结点。我们需要一个辅助指针来进行出队,该指针初始指向尾节点。报数相当于移动头结点和辅助指针,头结点到出队的那一个节点,将辅助指针的next指向头结点的next便完成了出队。然后将辅助指针的next作为头结点即可,直到只剩下最后一个节点。及头结点和辅助指针指向的节点是同一个接点。
public void josephPop(int beginNo, int readNum) { if (head == null) { return; } Child helper = head; while (true) { if (helper.getNext() == head) { break; } helper = helper.getNext(); } for (int i = 1; i < beginNo; i++) { head = head.getNext(); helper = helper.getNext(); } while (head != helper) { for (int i = 0; i < readNum - 1; i++) { head = head.getNext(); helper = helper.getNext(); } System.out.println(head.getNo()); helper.setNext(head.getNext()); head = helper.getNext(); } System.out.println(helper.getNo()); }
至此约瑟夫环及约瑟夫问题模拟如下:
class CircleSingleLinkedList { private Child head; public void init(int n) { Child cur; if (n < 1) { return; } else if (n == 1) { head = new Child(1); head.setNext(head); } else { head = new Child(1); head.setNext(head); cur = head; for (int i = 2; i <= n; i++) { cur = cur.getNext(); Child cd = new Child(i); cur.setNext(cd); cd.setNext(head); } } } public void addLast(Child child) { Child cur = head; while (cur.getNext() != head) { if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在!!"); } cur = cur.getNext(); } if (cur.getNo()==child.getNo()){ throw new RuntimeException("编号已存在!!"); } cur.setNext(child); child.setNext(head); } public void show() { if (head == null) { return; } if (head.getNext() == head) { System.out.println(head.getNo()); return; } Child cur = head; while (cur.getNext() != head) { System.out.println(cur.getNo()); cur = cur.getNext(); } System.out.println(cur.getNo()); } public void delete(int no) { if (head == null) { return; } Child cur = head; while (cur.getNext() != head) { if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); return; } cur = cur.getNext(); } if (cur.getNext().getNo() == no) { cur.setNext(cur.getNext().getNext()); head = cur.getNext(); } } public void josephPop(int beginNo, int readNum) { if (head == null) { return; } Child helper = head; while (true) { if (helper.getNext() == head) { break; } helper = helper.getNext(); } for (int i = 1; i < beginNo; i++) { head = head.getNext(); helper = helper.getNext(); } while (head != helper) { for (int i = 0; i < readNum - 1; i++) { head = head.getNext(); helper = helper.getNext(); } System.out.println(head.getNo()); helper.setNext(head.getNext()); head = helper.getNext(); } System.out.println(helper.getNo()); } }
测试
创建一个5个节点的约瑟夫环,从第一个节点开始报数,每次报3个数,出队顺序如下:
public static void main(String[] args) { CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); circleSingleLinkedList.init(5); circleSingleLinkedList.josephPop(1, 3); }
出队顺序为:3 1 5 2 4
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Python 的整数与 Numpy 的数据溢出
某位 A 同学发了我一张截图,问为何结果中出现了负数? 看了图,我第一感觉就是数据溢出了。数据超出能表示的最大值,就会出现奇奇怪怪的结果。 然后,他继续发了张图,内容是 print(100000*208378),就是直接打印上图的 E[0]*G[0],结果是 20837800000,这是个正确的结果。 所以新的问题是:如果说上图的数据溢出了,为何直接相乘的数却没有溢出? 由于我一直忽视数据的表示规则(整型的上限是多少?),而且对 Numpy 了解不多,还错看了图中结果,误以为每一个数据都是错误的,所以就解答不出来。 最后,经过学习群里的一番讨论,我才终于明白是怎么回事,所以本文把相关知识点做个梳理。 在正式开始之前,先总结一下上图会引出的话题: Python 3 中整数的上限是多少?Python 2 呢? Numpy 中整数的上限是多少?出现整数溢出该怎么办? 关于第一个问题,先看看 Python 2,它有两种整数: 一种是短整数,也即常说的整数,用 int 表示,有个内置函数 int()。其大小有限,可通过sys.maxint() 查看(取决于平台是 32 位还是 64 位) 一种是...
- 下一篇
简述下Vue组件化封装过程?
概念 组件系统是 Vue 的另一个重要概念,因为它是一种抽象,允许我们使用小型、独立和通常可复用的组件构建大型应用。仔细想想,几乎任意类型的应用界面都可以抽象为一个组件树: !!! 熟记 : 页面中可复用的结构、样式和功能,抽离成一个文件; 特点: 为了便于 组织和管理代码 , 便于维护和扩展维护 组件化和模块化的不同: 模块化:是从代码逻辑的角度进行划分的;方便代码分层开发,保证每个功能模块的职能单一 组件化:是从UI界面的角度进行划分的前端的组件化方便组件的重用; 全局组件 这些组件是全局注册的。也就是说它们在注册之后可以用在任何新创建的 Vue 根实例 (new Vue) 的模板中。 1. 注册 Vue.component('MyDemo'{ template:`<div>这个的全局组件的注册</div>` }) 2.实例化 Vue var vm = new Vue({ el:'#app', }) 3. 使用组件 <div id="app"> <my-demo></my-demo> </div> !!!注意事...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS6,CentOS7官方镜像安装Oracle11G
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Hadoop3单机部署,实现最简伪集群
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果