package com.qingfeng;
/**
* @author Administrator
* 功能:约瑟夫问题:
* 设编号分别为:1,2,...,n的n个人围坐一圈。
* 约定序号为k(1 <= k < = n)的人从1开始计数,数到m的那个人出列,
* 他的下一位又从1开始计数,数到m的那个人又出列,依次类推,直到所有人出列为止。
*/
public class Josephus { public static void main(String[] args) {
// TODO Auto-generated method stub
KidLink kid = new KidLink();
kid.setLength(5);
kid.creatLink();
kid.setM(2);
kid.setK(3); kid.show();
kid.play();
}
}
//孩子类
class Kid
{
//成员变量
int no;//孩子编号
Kid nextKid;//下一个孩子的引用 关键点! //构造方法
public Kid(int no)//设置孩子的编号
{
this.no = no;
}
} //孩子环形链表类
class KidLink
{
//成员变量
Kid firstKid;//第一个孩子的引用 不能动!!关键点! int i;
int len;//圈的长度:多少个人 Kid temp;//跑龙套 int m;//约定开始数数的那个人
int k;//约定数几下出圈 //成员方法
//设置循环链表的长度即
public void setLength(int len)
{
this.len = len;
} //1.创建孩子3.连成环状
public void creatLink()
{
for(i=1; i<=len; i++)
{
if(i==1)//第一个孩子
{
Kid ch = new Kid(i);//创建第一个孩子 ch为第一个孩子的引用
firstKid = ch;//firstKid指向第一个孩子!
temp = ch;//跑龙套temp也指向当前孩子!
}
else
{
if(i == len)//最后一个孩子
{
Kid ch = new Kid(i);//创建最后一个孩子
temp.nextKid = ch;
temp = ch;
temp.nextKid = firstKid;
}
else
{
Kid ch = new Kid(i);//创建剩余的孩子
temp.nextKid = ch;//跑龙套(孩子的引用)的下一个孩子(相当于next指针)指向当前 孩子!
temp = ch;//跑龙套指向新的当前孩子!
}
}
}
}
//打印孩子编号即围成的圈
public void show()
{
temp = firstKid;
do{
System.out.print(temp.no+" ");
temp = temp.nextKid;
}while(temp!= firstKid);//理解do while的好处
} //设置m的值
public void setM(int m)
{
this.m = m;
}
//设置n的值
public void setK(int k)
{
this.k = k;
}
//开始玩游戏
public void play()
{
temp = firstKid;
//1.先找到数数的那个人m
for(i=1; i<m; i++)//易错!不是"等于"
{
temp = temp.nextKid;
}
while(len!=1){
System.out.print(" m的值为"+temp.no);
//2.数n下找到出圈的人即temp
for(i=1; i<k; i++)//易错!不是"等于"
{
temp = temp.nextKid;
}
//3.temp退圈
//先找到temp的前一个人即temp2
Kid temp2;
temp2 =temp;
while(temp2.nextKid != temp)
{
temp2 = temp2.nextKid;
}
temp2.nextKid = temp.nextKid; //删除语句 如第二人指向第四个人
System.out.print(" 出圈人"+temp.no);
temp = temp.nextKid;//开始数数的人temp指向被删的下一个 len--;//每次少一个人
}
System.out.println(" 最后出圈的是"+temp.no);
}
}
05-19 13:00
查看更多