数据结构丢手帕问题 - 黑马程序员技术交流社区

//数据结构约瑟夫问题
/*用java实现的丢手帕问题，即有n个人围成圈，从第k个人开始从1报数，
报到第m个人时出局，从出局人的下一个开始从新报数，
报到第m个人时出局......如此循环直至最后一人出局*/
class Child {
int no; //编号
Child nextChileChild = null; //指向下一个人
public Child(int no) {
this.no = no;
}
}
//链表类
//环形链表
class CycLink {
//先定义一个指向链表第一个小孩的那个引用
//指向第一个小孩的引用，不能动
Child firstChild = null;
Child temp = null;
int len = 0;// 表示共有几个小孩
int k;
int m;
//设置链表大小
public void setLen(int len) {
this.len = len;
}
public void setK(int k) {
//设置第几个人开始数数
this.k = k;
}
public void setM(int m) {
//设置m
this.m = m;
}
public void play() {
//1找到开始数数的人
Child temp = this.firstChild;
for (int i = 1; i < k; i++) {
temp = temp.nextChileChild;
}
//数M下
while (this.len != 1) {
for (int j = 1; j < m; j++) {
temp = temp.nextChileChild;
}
Child temp2 = temp;// 找到要出圈的前一个小孩
//讲数到M的小孩退出圈
temp2=temp2.nextChileChild;
temp.nextChileChild=temp2.nextChileChild;
System.out.println("现在出圈的是" + temp2.no);
this.len--;
}
//打印最优一个小孩
System.out.print("最后出圈的是：" + temp.no);
}
//初始化链表
public void creatLink() {
for (int i = 1; i <= len; i++) {
if (i == 1) {
//创建第一小孩
Child child = new Child(i);
this.firstChild = child;
this.temp = child;
} else {
if (i == len) {
Child child = new Child(i);
temp.nextChileChild = child;
temp = child;
temp.nextChileChild = this.firstChild;
} else {
//继续创建小孩
Child child = new Child(i);
temp.nextChileChild = child;
temp = child;
}
}
}
}
public void show() {
Child temChild = this.firstChild;
do {
System.out.println(temChild.no + "###");
temChild = temChild.nextChileChild;
} while (temChild != this.firstChild);
}
}
//主方法类
public class Demo4 {
public static void main(String[] args) {
//TODO Auto-generated method stub
CycLink cyclink =new CycLink();
cyclink.setLen(17);
cyclink.creatLink();
cyclink.setK(17);//17代表尾号//从1号开始念
cyclink.setM(3);//输出念到3的人出圈
cyclink.show();
cyclink.play();
}
}

复制代码