文章目录

约瑟夫问题:解题思路：定义孩子节点：创建循环单链表：遍历循环单链表：根据用户的输入，计算出小孩出圈的顺序：最后就是程序的运行啦：

约瑟夫问题:

约瑟夫问题（有时也称为约瑟夫斯置换，是一个计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.） 其一般形式：约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

问题来历：

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 [1] 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

以上资料均来自------约瑟夫问题_百度百科

我们在这里把问题简化成：N个孩子围成一圈，从第k个孩子开始报数，每次从一开始报数，报到M的孩子出列，下一个孩子继续从1开始报数，直到剩下最后一个孩子，在此期间，我们要打印出出队的孩子的编号。 我们可以用单向循环链表和利用数组，对数组下标进行取模运算来解决此问题，在这里我们只用单向循环链表来解决此问题。

解题思路：

假设此时N=5，k=1，M=2

按照孩子的编号创建一个没有头节点的单向循环链表，first代表的是第一个报数的孩子 将first指向的指定的第一个报数的孩子（first = first.next执行k-1次，注意不是执行k次，这是因为第一个孩子本身也要报数），在我们假定的情况下，first不需要移动。创建一个辅助指针helper，事先让这个指针指向最后一个节点（判断条件：helper==first） 当小孩报数时，helper和first同时移动M-1次

,这时候，first所指向的孩子就是要出列的孩子

将first所指向的孩子的编号进行打印出列的操作：实际上就是循环队列的删除节点的操作： first = first.next; helper.next = first

附上源码：

定义孩子节点：

class Boy { private int number;//孩子的编号 private Boy next;//next是指向下一个孩子 public Boy() {} public Boy(int number) { this.number = number; } public void setNumber(int number) { this.number = number; } public int getNumber() { return number; } public void setNext(Boy next) { this.next = next; } public Boy getNext() { return next; } }

创建循环单链表类，并在里面定义创建没有头节点的循环单链表的方法，和打印出列的孩子的方法，和遍历整条循环单链表的方法：

创建循环单链表：

private Boy first = null;//first是CircleSingleLinkedList类的私有属性，代表的是第一个报数的孩子 public void addBoy(int sum) { if(sum<2) {//对sum进行数据校验 throw new RuntimeException("输入的数据不符合逻辑！"); } Boy curBoy = null;//curBoy是一个辅助指针，用于指向当下的循环链表中的最后一个节点，这有点像用尾插法创建单链表中的始终指向链表中最后一个节点的tail尾指针 for(int i=1; i<=sum; i++) { Boy boy = new Boy(i);//创建新的孩子节点 if(i==1) {//当循环链表只有一个孩子节点时，其next域要指向自己 first = boy; first.setNext(first); curBoy = boy; }else {//当循环单链表中含有不止一个孩子节点： curBoy.setNext(boy); curBoy = boy; curBoy.setNext(first); } } }

遍历循环单链表：

public void showBoy() { if(first==null) { System.out.println("此循环链表为空！不能进行遍历操作！！"); return; }else { Boy cur = first; /*本人一开始的错误方法： 这种方法遍历的小孩总数总是会比所有小孩总数少一 while(cur.getNext()!=first) { System.out.println("小孩的编号为："+cur.getNumber()); cur = cur.getNext(); }*/ while(true) { System.out.println("小孩的编号为："+cur.getNumber()); if(cur.getNext()==first) { break; } cur = cur.getNext(); } } }

根据用户的输入，计算出小孩出圈的顺序：

startNumber表示从编号为startNumber的孩子开始报数, countNumber表示从1一直报到countNumber, sum表示孩子的总数

public void countBoy(int startNumber, int countNumber, int sum) { addBoy(sum);//创建循环单链表 if(first==null || startNumber<1 || startNumber>sum) {//先对传入的实参进行校验 throw new RuntimeException("输入的数据有误！！"); } //把first指针指向第一个报数的孩子 for(int i=1; i<startNumber; i++) { first = first.getNext(); } //创建辅助指针，并让辅助指针指向循环单链表的最后一个孩子节点 Boy helper = first; while(helper.getNext()!=first) { helper = helper.getNext(); } while(true) { if(first==helper) {//此时只剩下了一个孩子节点 break; }else { for(int i=1; i<countNumber; i++) {//对first和helper的移位操作 first = first.getNext(); helper = helper.getNext(); } System.out.println("出圈的小孩的编号为："+first.getNumber()); first = first.getNext();//删除孩子节点操作 helper.setNext(first);; } } System.out.println("最后留下的小孩编号为：" + first.getNumber()); }

最后就是程序的运行啦：

public class Josepfu { public static void main(String[] args) { CircleSingleLinkedList list = new CircleSingleLinkedList(); list.countBoy(10, 20, 125); } }