数据结构|数据结构（循环链表解决约瑟夫问题）链表|数据结构|单链表

- 约瑟夫问题
- - 问题来历
  - 循环链表进行模拟
  - 思路

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

文章图片

循环链表进行模拟
因为约瑟夫问题是一个环状，因此又被称为约瑟夫环，结构与循环链表相似，因此可以用循环链表进行模拟。
思路

创建节点

class Person { //序号 private int num; //后继指针,指向下一个节点 private Person next; public Person(int num) { this.num = num; }public int getNum() { return num; }public void setNum(int num) { this.num = num; }public Person getNext() { return next; }public void setNext(Person next) { this.next = next; } }
创建一个单向的环形链表
1. 先创建第一个头节点，并让first指针指向该节点，next指针指向本身，形成环状。
2. 后面每创建一个新的节点，就把其加到已有的环形链表中。
/** * 单向的环形链表 */ class CircleSingleLinkedList { /** * 创建一个first节点 */ private Person first; /** * 添加节点构建环形链表 * @param nums 要创建的节点个数 */ public void addPerson(int nums) { if (nums < 1) { System.out.println("nums值不正确！"); return; } //帮助构建环形链表 Person temp = null; //使用for来创建我们的环形链表 for (int i = 1; i <= nums ; i++) { //根据编号创建节点 Person person = new Person(i); //头节点 if (i == 1) { first = person; //构成环状 first.setNext(first); //让指针指向第一个节点 temp = first; continue; } temp.setNext(person); person.setNext(first); temp = person; } } }
遍历环形链表
1. 先让一个辅助指针temp指向first头节点
2. 通过while循环遍历该环形链表
public void list() { if (first == null) { System.out.println("空链表"); return; } //头节点不能动,用辅助指针来实现遍历 Person temp = first; while (true) { System.out.printf("编号:%d\n",temp.getNum()); //遍历完毕 if (temp.getNext() == first) { break; } //指针后移 temp = temp.getNext(); } }
计算各个节点出表顺序
1. 创建一个辅助指针end指向链表的最后一个节点
2. 根据起始报数位置startNum，让first和end指针同时移动startNum-1次
3. 开始报数，每次报数让first和end指针向后移动countNums-1次
4. 最后first指针指向的节点就是要出表的节点
5. 移出该节点，重复34步骤。
  
  文章图片
/** * 根据用户的输入计算出人出圈的顺序 * @param startNum表示从第几个人开始报数 * @param countNums表示每次数几次 * @param personNums表示最初有多少人 */ public void play(int startNum,int countNums,int personNums) { if (first == null || startNum < 1 || startNum > personNums) { System.out.println("参数输入有误，请重新输入"); return; }//创建辅助指针 Person end = first; //开始报数之前让end指针指向最后一个节点 while (true) { if (end.getNext() == first) { break; } end = end.getNext(); }//报数前让first和end根据startNum进行校准 for (int i = 0; i < startNum - 1; i++) { first = first.getNext(); end = end.getNext(); }//报数时，让first和end指针同时移动(countNums-1)次 while (true) { //圈中只有一个节点 if (end == first) { break; } for (int i = 0; i < countNums - 1; i++) { first = first.getNext(); end = end.getNext(); } System.out.printf("出圈号码:%d\n",first.getNum()); first = first.getNext(); end.setNext(first); } System.out.printf("最后留在圈中的号码是：%d\n",first.getNum()); }

测试

public class Josephu { public static void main(String[] args) { CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); //添加节点 circleSingleLinkedList.addPerson(6); //遍历链表 circleSingleLinkedList.list(); //计算出圈顺序并输出 circleSingleLinkedList.play(1,5,6); } } ------------------------------------------------------------------------------------------------------------------- //输出结果: 编号:1 编号:2 编号:3 编号:4 编号:5 编号:6 出圈号码:5 出圈号码:4 出圈号码:6 出圈号码:2 出圈号码:3 最后留在圈中的号码是：1 5->4->6->2->3->1

【数据结构|数据结构（循环链表解决约瑟夫问题）】如有错误或不足欢迎评论指正。