约瑟夫环变种问题——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=\ }

//找出将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

//一直找，直到剩下k个好人 while (this.len!=lenTemp/2){ //数m下 for(int j=1;j

}

{ 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=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;

}

}

}

}

temp.nextchild=this.firstChild; } 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 );