Josephu问题为：
设置编号为1,2,3，......n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1看是报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示：用有个不带头的循环链表来处理Josephu问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
代码：
public class Demo{ public static void main(String[] args){ CycLink cyclink=new CycLink(); cyclink.setLen(5); cycLink.createLink(); cyclink.show(); } } //小孩 class Child{ //编号 int no; //结点 Child nextChild=null; public Child(int no){ //给编号 this.no=no; } } //环形链表 class CycLink{ //先定义一个指向链表第一个小孩的引用 //指定第一个小孩的引用不能动，不然以后找不到他了 Child firstChild=null; //定义一个游标 Child temp=null; //表示共有几个小孩 int len=0; //设置链表大小 public void setLen(int len){ this.len=len; } //初始化环形链表 public void createLink(){ for(int i=1;i<=len;i++){ if(i==1){ //创建第一个小孩 Child ch=new Child(i); this.firstChild=ch; this.temp=ch; }else{ //创建最后一个小孩 if(i==len){ Child ch=new Child(i); temp.nextChild=ch; temp=ch; temp.nextChild=this.firstChild; }else{ //继续创建小孩 Child ch=new Child(i); //连接，搭桥 temp.nextChild=ch; //temp向前走一步，指向刚刚进来的孩子 temp=ch; } } } } //打印该环形链表 public void show(){ Child temp=this.firstChild; do{ System.out.println(temp.no); temp=temp.nextChild; }while(temp!=this.fistChild); } }
优化：
代码：
public class Demo{ public static void main(String[] args){ CycLink cyclink=new CycLink(); cyclink.setLen(50); cycLink.createLink(); cycLink.setK(2); cycLink.setM(3); cyclink.show(); cyclink.play(); } } //小孩 class Child{ //编号 int no; //结点 Child nextChild=null; public Child(int no){ //给编号 this.no=no; } } //环形链表 class CycLink{ //先定义一个指向链表第一个小孩的引用 //指定第一个小孩的引用不能动，不然以后找不到他了 Child firstChild=null; //定义一个游标 Child temp=null; //表示共有几个小孩 int len=0; int k=0; int m=0; //设置m public void setM(int m){ this.m=m; } //设置链表大小 public void setLen(int len){ this.len=len; } //设置从第几个人开始数数 public void setK(int k){ this.k=k; } //开始play public void play(){ Child temp=this.fistChild; //1.先找到开始数数的人 //int i=1;i<k;因为自己也要数一下，所以i不能为k for(int i=1;i<k;i++){ temp=temp.nexChild; } while(this.len!=1){ //2.数m下 for(int j=1;j<m;j++){ temp=temp.nextChild; } //找到要出圈的前一个小孩，有待优化 Child temp2=temp; while(temp2.nextChild!=temp){ temp2=temp2.nextChild; } //3.将数到m的小孩，退出圈 temp2.nextChild=temp.nextChild; //让temp指向数数的小孩 temp=temp.nextChild; this.len--; } //最后一个小孩（验证） System.out.println(temp.no); } //初始化环形链表 public void createLink(){ for(int i=1;i<=len;i++){ if(i==1){ //创建第一个小孩 Child ch=new Child(i); this.firstChild=ch; this.temp=ch; }else{ //创建最后一个小孩 if(i==len){ Child ch=new Child(i); temp.nextChild=ch; temp=ch; temp.nextChild=this.firstChild; }else{ //继续创建小孩 Child ch=new Child(i); //连接，搭桥 temp.nextChild=ch; //temp向前走一步，指向刚刚进来的孩子 temp=ch; } } } } //打印该环形链表 public void show(){ Child temp=this.firstChild; do{ System.out.println(temp.no); temp=temp.nextChild; }while(temp!=this.fistChild); } }