/约瑟夫问题（丢手帕）
//设编号为1,2,3…n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始
//报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出
//列，依次列推，知道所有人出列为止，由此产生一个出对编号的序列
package com;
public class Demo3 {
public static void main(String[] args){
Cyclink cyclink=new Cyclink();
cyclink.setLen(9);
cyclink.setK(1);
cyclink.setM(1);
cyclink.createLint();
cyclink.show();
cyclink.play();
}
}
class Child{
int no;
Child nextChiled=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;
//设置链表大小
public void setLen(int len){
this.len=len;
}
public void setK(int k){
this.k=k;
}
public void setM(int m){
this.m=m;
}
//开始play
public void play(){
Child temp=this.firstChild;
Child temp2=temp;
//1.先找到开始数数的人
for(int i=1;i<k;i++){
temp=temp.nextChiled;
}
while(this.len!=1){
//2.数m下
for(int j=1;j<m;j++){
temp2=temp;
temp=temp.nextChiled;
}
//找到要出圈的前一个小孩
// Child temp2=temp;
// while(temp2.nextChiled!=temp){
// temp2=temp2.nextChiled;
// }
//3.将数到m的小孩，退出圈
temp2.nextChiled=temp.nextChiled;
//让temp指向下一个数数的小孩
temp=temp.nextChiled;
this.len–;
}
//最后一个小孩
System.out.println(“最后是”+temp.no);
}
// 初始化环形链表
public void createLint(){
for(int i=1; i<=len; i++){
//创建第一个小孩
if(i==1){
Child ch=new Child(i);
this.firstChild=ch;
this.temp=ch;
}
else if(i>1 & &i<len){
Child ch=new Child(i);
temp.nextChiled=ch;
temp=ch;
}
else{
Child ch=new Child(i);
temp.nextChiled=ch;
temp=ch;
temp.nextChiled=this.firstChild;
}
}
}
public void show(){
Child temp=this.firstChild;
do{
System.out.print(temp.no+” “);
temp=temp.nextChiled;
}while(temp!=this.firstChild);
}
}
