第一篇：約瑟夫環(huán)變種問題——k個(gè)好人k個(gè)壞人

/*功能：約瑟夫變種問題

假如有k個(gè)好人，和k個(gè)壞人，所有人站成一圈，前K個(gè)人是好人，后K個(gè)人是壞人，編寫程序計(jì)算一個(gè)最小的m,使k個(gè)壞人都被處死，而不處決任何好人。

本程序基于韓順平Java約瑟夫環(huán)程序！

*/

public class Demo

{

public static void main(String[] args)

{

int m=ysminm(2);//該圈中有2個(gè)好人和2個(gè)壞人

System.out.println(“將壞人殺死的最小的m=”+m);

}

//找出將k個(gè)壞人殺死的最小m

public static int ysminm(int k)

{

int temp=1;

int m=1;

while(true)

{

CycLink cyclink=new CycLink();

cyclink.setLen(2*k);//設(shè)置環(huán)為k個(gè)好人和k個(gè)壞人

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){

//給一個(gè)編號(hào)this.no=no;}

}

//環(huán)形鏈表 class CycLink {

//先定義一個(gè)指向鏈表第一個(gè)人的引用 Child firstChild=null;Child temp=null;int len=0;//表示共有幾個(gè)人 int k=0;//表示從第幾個(gè)開始數(shù) int m=0;//表示第幾個(gè)人別殺死//設(shè)置鏈表大小 public void setLen(int len){this.len=len;} //設(shè)置從第幾個(gè)人開始數(shù)數(shù) 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.先找到開始數(shù)數(shù)的人 for(int i=1;i

}temp=temp.nextchild;} //找到要?dú)⑺赖那耙粋€(gè)人 Child temp2=temp;while(temp2.nextchild!= temp){temp2=temp2.nextchild;} //3.將數(shù)到m的人殺死，推出圈 temp2.nextchild=temp.nextchild;// 如果殺死的人是好人，就表示m設(shè)置的不正確，返回false if(temp.no>=1&&temp.no<=lenTemp/2){return false;} //讓temp指向下一個(gè)數(shù)數(shù)的人 System.out.println(“第”+temp.no+“ 個(gè)人出局”);temp=temp.nextchild;this.len--;} //運(yùn)行到此處表明殺死的都是壞人，所以返回true.return true;//初始化環(huán)形鏈表 public void createLink(){for(int i=1;i<=len;i++){if(i==1){//創(chuàng)建第一個(gè)人Child ch=new Child(i);this.firstChild=ch;this.temp=ch;}else{//創(chuàng)建最后一個(gè)人if(i==len){//繼續(xù)創(chuàng)建人Child ch=new Child(i);temp.nextchild=ch;temp=ch;

}}}} } else {} //繼續(xù)創(chuàng)建人 Child ch=new Child(i);temp.nextchild=ch;temp=ch;//打印該環(huán)形鏈表 public void show(){} //定義一個(gè)跑龍?zhí)椎?Child temp=this.firstChild;do{System.out.println(temp.no);temp=temp.nextchild;}while(temp!= this.firstChild);