Josephu(约瑟夫、约瑟夫环) 问题
设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
例如：
n = 5 , 即有5个人
k = 1, 从第一个人开始报数
m = 2, 数2下
此时结果为 2->4->1->5->3
提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，
然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个
结点又从1开始计数，直到最后一个结点从链表中删除算法结束。构建一个单向的环形链表思路：
1. 先创建第一个节点, 让 first 指向该节点，并形成环形
2. 后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.
遍历环形链表的思路：
1. 先让一个辅助指针(变量) cur，指向first节点
2. 然后通过一个while循环遍历 该环形链表即可 cur.next == first 结束
代码演示：
我们首先定义一个Boy节点类：
//Boy节点
class Boy{
private int No;//编号
private String name;//名字
private Boy next;//指针
public Boy(int no, String name) {
No = no;
this.name = name;
}
public int getNo() {
return No;
}
public void setNo(int no) {
No = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
@Override
public String toString() {
return "Boy{" +
"No=" + No +
", name='" + name + '\'' +
'}';
}
}然后定义循环链表类
class CircleSingleLinkedList{
boolean flag=false; //链表为空时flag=0，不为空时为1
Boy cur = null ;//cur节点指向当前的节点
private Boy first=null;//first节点始终指向第一个节点
public Boy getFirst() {
return first;
}
public void addBoy(Boy boy){
//如果链表为空，就让first、cur都指向新节点，first的next指向它自身，构成循环结构
if(!flag) {
first = boy;
first.setNext(boy);
cur=first;
flag=!flag;
}else{
//如果链表不为空，就让cur的next指向新节点，新节点的next指向first，最后让cur指向新节点。构成新的循环结构
cur.setNext(boy);
boy.setNext(first);
cur=boy;
flag=true;
}
}
//辅助遍历遍历链表，直到遍历回first结束。
public void showBoy(){
if(first==null) return;
Boy temp=first;
while(true){
System.out.println(temp);
temp=temp.getNext();
if(temp==first)break;
}
}
}约瑟夫问题的代码思路：
1. 创建一个辅助变量 helper , 事先指向环形链表的最后这个节点.，first仍然指向第一个节点
2. 小孩报数前，先让 first 和 helper 移动 k - 1次
2. 当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次
3. 这时就可以将first 指向的小孩节点 出圈
first = first .next
helper.next = first
原来first 指向的节点就没有任何引用，就会被回收。再循环第2步就可以，直到first == helper
@Test
public void Josepfu(){
//Initialize a circleList which has 5 nodes
CircleSingleLinkedList circleList=new CircleSingleLinkedList();
circleList.addBoy(new Boy(1,"wz"));
circleList.addBoy(new Boy(2,"zp"));
circleList.addBoy(new Boy(3,"lf"));
circleList.addBoy(new Boy(4,"zl"));
circleList.addBoy(new Boy(5,"hz"));
circleList.showBoy();
int startNo=1;//开始的位置序号，从几号开始数？
int countNum=2;//每次数几个?
//最开始first指向首个节点
Boy first=circleList.getFirst();
Boy helper=first;
//让helper指向最后一个节点
while(true){
if(helper.getNext()==first)break;
helper=helper.getNext();
}
//根据开始的位置移动first、helper，使它们始终指向startNo序号对应的节点和它前面的节点
for(int i=0;i<(startNo-1);i++){
first=first.getNext();
helper=helper.getNext();
}
//每次移动countNum位，移除该位的节点，然后从下一位再重新移动countNum位...
while(true){
//只剩一个节点了
if(helper==first) break;
//移动first、helper,移动结束后移除first对应的节点
for(int i=0;i<(countNum-1);i++){
first=first.getNext();
helper=helper.getNext();
}
System.out.print(first.getNo()+"->");
//first、helper都后移一位，然后重新开始数
first = first.getNext();
helper.setNext(first);
}
System.out.print(first.getNo());
}
测试结果：
Boy{No=1, name='wz'}
Boy{No=2, name='zp'}
Boy{No=3, name='lf'}
Boy{No=4, name='zl'}
Boy{No=5, name='hz'}
2->4->1->5->3