第一帖，约瑟夫问题，帮忙优化优化 - 黑马程序员技术交流社区

/*
* 有n个孩子站成一圈，从第一个孩子开始顺时针方向报数，
* 报到3的人出列，下一个人继续从1报数，直到最后剩下
* 一个孩子为止。问剩下第几个孩子。下面的程序以10个
* 孩子为例，模拟了这个过程，请完善之（提示：报数的
* 过程被与之逻辑等价的更容易操作的过程所代替）。
*
* 方法一（蓝桥杯给出的方法）：
* 数到不是出列的孩子删除并把这个孩子加到队列的最后，
* 数到出列的孩子直接删除，直到只剩下最后一个孩子为止
* Vector a = new Vector();
for(int i=1; i<=10; i++)
{
a.add("第" + i + "个孩子");
}
for(;;)
{
if(a.size()==1) break;
for(int k=0; k<2; k++)
a.add(a.remove(0));
a.remove(0);
}
System.out.println(a);
*
* */
//方法二：利用引用来模拟出循环链表来决解
//这一个方法可以灵活变通，可以从随机一个孩子开始数
class Peoson{//定义一个孩子类
int num; //孩子编号
static int count=0; //正在游戏中的孩子总数
Peoson getNext=null;//本类的引用，用来指向下一个孩子.
Peoson(int num){
count++; //每创建一个孩子加1
this.num=num;
}
}
public class BaoshuGame {
public static void main(String[] args) {
Peoson p=new Peoson(1); //创建第一个孩子//
Peoson p1=p; //p1表示指针，开始p1为第一个孩子
for (int i = 2; i <= 10; i++) {
//从第二个孩子开始创建，并且前一个孩子指向下一个孩子
Peoson p2=new Peoson(i);//创建孩子对象
p1.getNext=p2; //p1指向这个孩子
p1=p2; //p1变为这个孩子（和p1指向这个孩子是不同的概念，这里实现了p1的移动）
}
p1.getNext=p; //到这为止，p1为最后一个孩子，并指向第一个孩子，循环链表已经形成
//下面开始报数
/*
* 实现过程是：报到的孩子出列，即这个孩子的前一个孩子指向这个孩子的下一个孩子，让
* 这个孩子成为野孩子
* */
while(Peoson.count!=1){
Peoson p2=null;
for (int i = 1; i < 3; i++) {
p2=p;
p=p.getNext;
}
//循环两次后p为第三个孩子了，即要出列的孩子，p2为出列孩子的前一个孩子
p2.getNext=p.getNext;//出列孩子的前一个孩子指向出列孩子的下一个孩子
p=p.getNext;//从出列孩子的下一个孩子开始
Peoson.count--;//孩子个数减1
}
System.out.println(p.num);//打印最后一个孩子的编号，游戏结束
}
}

复制代码