约瑟夫环变种问题——k个好人k个坏人

第一篇：约瑟夫环变种问题——k个好人k个坏人

/*功能：约瑟夫变种问题

假如有k个好人，和k个坏人，所有人站成一圈，前K个人是好人，后K个人是坏人，编写程序计算一个最小的m,使k个坏人都被处死，而不处决任何好人。

本程序基于韩顺平Java约瑟夫环程序！

*/

public class Demo

{

public static void main(String[] args)

{

int m=ysminm(2);//该圈中有2个好人和2个坏人

System.out.println(“将坏人杀死的最小的m=”+m);

}

//找出将k个坏人杀死的最小m

public static int ysminm(int k)

{

int temp=1;

int m=1;

while(true)

{

CycLink cyclink=new CycLink();

cyclink.setLen(2*k);//设置环为k个好人和k个坏人

cyclink.createLink();

cyclink.setK(temp);

cyclink.setM(m);

cyclink.show();

if(cyclink.play())

{

return m;

}

m++;

}

}

}

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;//表示第几个人别杀死//设置链表大小 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，如果找到m则返回true,否则返回false.public boolean play(){int lenTemp=len;Child temp=this.firstChild;//1.先找到开始数数的人 for(int i=1;i

}temp=temp.nextchild;} //找到要杀死的前一个人 Child temp2=temp;while(temp2.nextchild!= temp){temp2=temp2.nextchild;} //3.将数到m的人杀死，推出圈 temp2.nextchild=temp.nextchild;// 如果杀死的人是好人，就表示m设置的不正确，返回false if(temp.no>=1&&temp.no<=lenTemp/2){return false;} //让temp指向下一个数数的人 System.out.println(“第”+temp.no+“ 个人出局”);temp=temp.nextchild;this.len--;} //运行到此处表明杀死的都是坏人，所以返回true.return true;//初始化环形链表 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;

}}}} } else {} //继续创建人 Child ch=new Child(i);temp.nextchild=ch;temp=ch;//打印该环形链表 public void show(){} //定义一个跑龙套的 Child temp=this.firstChild;do{System.out.println(temp.no);temp=temp.nextchild;}while(temp!= this.firstChild);