约瑟夫问题

ReFly

浏览: 7337 次
性别:
来自: 资阳

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

package night;

public class Test1 {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
      Cyclink cyclink=new Cyclink();
      cyclink.setLen(5);
      cyclink.createLink();
      cyclink.setK(2);
      cyclink.setM(2);
      cyclink.show();
      cyclink.play();

                                       }
                  }

class Child {
int no;
Child nextchild;
public void Chlid(int no){     //构造方法，
this.no=no;
          }
           }

class Cyclink{                 //先定义一个指向第一个小孩的引用
Child firstChild=null;    //设置一个child
Child temp=null;         //设置一个临时的个体
int len=0;              //定义链表长度变量
int k=0;               //定义从哪一个个体开始数,从第k个开始数
int m=0;              //定义每隔几个开始数，每第m个删除

public void setLen(int len){//设置链表的大小
this.len=len;
}

public void setK(int k){//设置从第几个人开始数数
this.k=k;
}

public void setM(int m){//每隔几个删除一个元素
this.m=m;
}

public void play(){//实现找到并删除的过程


//将数到的小孩，删除，退出圈
    Child temp = this.firstChild;


for (int i = 1; i < k; i++) {//先找到开始数数的那个人，第k个人开始数
temp=temp.nextchild;
}
//

while(this.len!=1){
for (int j = 1; j< m; j++) { //数m下
temp=temp.nextchild;
}
//找到要出圈的前一个小孩

Child temp2=temp;
while((temp2.nextchild)!=temp){
temp2=temp2.nextchild;
}

temp2.nextchild=temp.nextchild;
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();
ch.Chlid(i);
this.firstChild=ch;
this.temp=ch;}
else{
if(i!=len){
//继续创建小孩
Child ch=new Child();
ch.Chlid(i);
temp.nextchild=ch;
temp=ch;}
else{
Child ch=new Child();
ch.Chlid(i);
temp.nextchild=ch;
temp=ch;
temp.nextchild=this.firstChild;
}
}
}
}

public void show(){
//定义一个临时工
Child temp=this.firstChild;
    do{
System.out.println(temp.no);
temp=temp.nextchild;
}while(temp!=this.firstChild );
        }
//初始化环形链表
}

分享到：