浅谈约瑟夫问题

浅谈约瑟夫问题

本篇内容都将会围绕“约瑟夫问题”谈起，约瑟夫问题，或称“约瑟夫环”，又名“丢手绢问题”。约瑟夫问题是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。

约瑟夫问题由来已久，而这个问题的解法也在不断改进，只是目前仍没有一个极其高效的算法（log 以内）解决这个问题。

17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行，直到仅余15个人为止。问怎样的排法，才能使每次投入大海的都是非教徒。

直接进入主题，什么是约瑟夫问题？约瑟夫问题：N个人围成一圈，从约定编号为K的人开始报数，第M个将被杀掉，依次类推，最后剩下一个，其余人都将被杀掉。

直接上图展示，初始化状态： 假设n=6，总共有6个人，k=1,从第一个人开始报数，m=5,每次数五个。

第一次报数：从一号开始，数五个数，1-2-3-4-5，数完五个数，五号被杀死，第一次报数后，剩余人数如下。

第二次报数： 从被杀死的五号的下一位开始报数，也就是六号，数五个数，6-1-2-3-4，数数完毕，四号被杀死，第二次报数后，剩余人数如下。

第三次报数： 从被杀死的四号的下一位开始报数，同样是六号，数五个数，6-1-2-3-6，数数完毕，六号被杀死，第三次报数后，剩余人数如下。

第四次报数： 从被杀死的六号的下一位开始报数，也就是一号，数五个数，1-2-3-1-2，数数完毕，二号被杀死，第四次报数后，剩余人数如下。

第五次报数： 从被杀死的二号的下一位开始报数，也就是三号，数五个数，3-1-3-1-3，数数完毕，三号被杀死，只剩下一号，Game Over!

代码实现

实现思路：用单向循环链表来表示圈，将人杀死后修改链表上的节点即可。

第一步：构建节点上对象。

class Person {
 // 人的编号
 private int no;
 // 指向下一个人
 private Person next;
 public Person(int no) {
 this.no = no;
 }
 public int getNo() {
 return no;
 }
 public void setNo(int no) {
 this.no = no;
 }
 public Person getNext() {
 return next;
 }
 public void setNext(Person next) {
 this.next = next;
 }
}

第二步：创建一个环形的单向链表，将带有编号的人组织起来。

class CircleSingleLinkedList {
 // 创建一个first节点,当前没有编号
 private Person first = null;
 // 往环形链表中添加人，persons表示添加的人数
 public void addPerson(int persons) {
 if (persons < 1) {
 System.out.println("persons的值异常");
 return;
 }
 // 辅助指针，帮助构建环形链表
 Person curPerson = null;
 // 往环形链表中添加人
 for (int i = 1; i <= persons; i++) {
 Person person = new Person(i);
 // 如果是第一次添加人
 if (i == 1) {
 first = person;
 first.setNext(first);
 curPerson = first;
 } else {
 curPerson.setNext(person);
 person.setNext(first);
 curPerson = person;
 }
 }
 }
}

第三步：实现数数的方法。

/**
 *
 * @param startNo
 * 表示从第几个人开始数数
 * @param countNum
 * 表示每次数几下
 * @param nums
 * 表示圈中的人数
 */
 public void startCount(int startNo, int countNum, int nums) {
 if (first == null || startNo < 1 || startNo > nums) {
 System.out.println("参数输入有误， 请重新输入");
 return;
 }
 // 辅助指针,当我们要退出时的依据，当helper == first时，退出
 Person helper = first;
 // 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
 while (true) {
 if (helper.getNext() == first) {
 break;
 }
 helper = helper.getNext();
 }
 // 报数开始前，先让first和helper移动 k - 1次
 for(int j = 0; j < startNo - 1; j++) {
 first = first.getNext();
 helper = helper.getNext();
 }
 // 报数开始时，让first和helper指针同时 的移动 m - 1 次, 然后first指向人被杀死，出圈
 // 这里是一个循环操作，直至圈中只有一个节点
 while(true) {
 // 当helper == first时，说明圈中只有一个节点
 if(helper == first) {
 break;
 }
 // 让 first 和 helper 指针同时移动 countNum - 1
 for(int j = 0; j < countNum - 1; j++) {
 first = first.getNext();
 helper = helper.getNext();
 }
 System.out.printf("第%d号人被杀死\n", first.getNo());
 // 出圈操作
 first = first.getNext();
 helper.setNext(first);
 }
 System.out.printf("最后留在圈中的人的编号是：%d \n", first.getNo());
 }