您现在的位置是:首页 > 文章详情

数据结构与算法之约瑟夫问题

日期:2019-09-10点击:698

约瑟夫问题介绍

据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

编程描述:

有N个孩子手拉手围成一圈,从第M个孩子开始报数,报到第K个孩子出队,然后从下一个孩子继续开始报数,问:所有孩子的出队顺序?
如下图:
image

约瑟夫问题的数据结构引出:
图 1-1:
10_09_56__09_11_2019

问:用什么数据结构来处理这个问题比较合适呢?
我们不妨将图1-1稍作处理,如下图1-2:

10_18_15__09_11_2019

如果我们将每一个小人看人一个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的方法实现:

  1. 初始化创建带有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

原文链接:https://yq.aliyun.com/articles/718047
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章