有n个孩子站成一圈，从第一个孩子开始顺时针方向报数，报到3的人出列，下一个人继续从1报数，直到最后剩下一个孩子为止。问剩下第几个孩子。
下面的程序以10个孩子为例，模拟了这个过程，请完善之（提示：报数的过程被与之逻辑等价的更容易操作的过程所代替）。

第一种方法（蓝桥杯给出的答案）：数到不是出列的孩子删除并把这个孩子加到队列的最后，数到出列的孩子直接删除，直到只剩下最后一个孩子为止

1. Vector a = new Vector();
   
2.                 for(int i=1; i<=10; i++)
   
3.                 {
   
4.                         a.add("第" + i + "个孩子");
   
5.                 }
   
6.                 for(;;)
   
7.                 {
   
8.                         if(a.size()==1) break;
   
9.                         for(int k=0; k<2; k++)
   
10.                                 a.add(a.remove(0));
    
11.                         a.remove(0);
    
12.                 }
    
13.                 System.out.println(a);

复制代码

第二中方法（看了韩顺平老师的视频我自己做的）：利用引用来模拟出循环链表来决解

1. class Peoson{//定义一个孩子类
   
2.         int num; //孩子编号
   
3.         static int count=0; //正在游戏中的孩子总数
   
4.         Peoson getNext=null;//本类的引用，用来指向下一个孩子.
   
5.         Peoson(int num){
   
6.                 count++; //每创建一个孩子加1
   
7.                 this.num=num;
   
8.         }
   
9. }
   
10. public class BaoshuGame {
    
11.         
    
12.         public static void main(String[] args) {
    
13.                 Peoson p=new Peoson(1); //创建第一个孩子//
    
14.                 Peoson p1=p; //p1表示指针，开始p1为第一个孩子
    
15.                 for (int i = 2; i <= 10; i++) {
    
16.                         //从第二个孩子开始创建，并且前一个孩子指向下一个孩子
    
17.                         Peoson p2=new Peoson(i);//创建孩子对象
    
18.                         p1.getNext=p2; //p1指向这个孩子
    
19.                         p1=p2; //p1变为这个孩子（和p1指向这个孩子是不同的概念，这里实现了p1的移动）
    
20.                 }
    
21.                 p1.getNext=p;  //到这为止，p1为最后一个孩子，并指向第一个孩子，循环链表已经形成
    
22.                
    
23.                 //下面开始报数
    
24.                 /*
    
25.                  * 实现过程是：报到的孩子出列，即这个孩子的前一个孩子指向这个孩子的下一个孩子，让
    
26.                  * 这个孩子成为野孩子
    
27.                  * */
    
28.                 while(Peoson.count!=1){
    
29.                         Peoson p2=null;
    
30.                         for (int i = 1; i < 3; i++) {
    
31.                                 p2=p;
    
32.                                 p=p.getNext;
    
33.                         }
    
34.                         //循环两次后p为第三个孩子了，即要出列的孩子，p2为出列孩子的前一个孩子
    
35.                         p2.getNext=p.getNext;//出列孩子的前一个孩子指向出列孩子的下一个孩子
    
36.                         p=p.getNext;//从出列孩子的下一个孩子开始
    
37.                         Peoson.count--;//孩子个数减1
    
38.                 }
    
39.                 System.out.println(p.num);//打印最后一个孩子的编号，游戏结束
    
40.         }
    
41. }
    

复制代码

1. import java.util.*;
   
2. 
   
3. public class Test2 {
   
4. 
   
5.         /**
   
6.          * 有n个孩子站成一圈，从第一个孩子开始顺时针方向报数，报到3的人出列，下一个人继续从1报数，直到最后剩下一个孩子为止。问剩下第几个孩子。
   
7.          * 下面的程序以10个孩子为例
   
8.          */
   
9.         public static void main(String[] args) {
   
10.                 int num =run(10);
    
11.                 System.out.println("剩下的是第"+num+"人");
    
12.         }
    
13. 
    
14.         public static int run(int a) {
    
15.                 List<Integer> list = new LinkedList<Integer>();
    
16.                 for (int i = 1; i <= a; i++) {
    
17.                         list.add(i);
    
18.                 }
    
19.                 int count = 1;
    
20.                 for (int j = 0; list.size() != 1; j++) {
    
21.                         if (j == list.size())
    
22.                                 j = 0;
    
23.                         if (count % 3 == 0)
    
24.                                 list.remove(j--);
    
25.                         count++;
    
26.                 }
    
27. 
    
28.                 return list.get(0);
    
29.         }
    
30. }

复制代码

这是我写的，楼主看看吧

上面用循环链表实约瑟夫问题，要模拟整个游戏过程，不仅程序写起来比较麻烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

这里用递推来写：

1. package cn.itcast;
   
2. 
   
3. public class Josephus {
   
4.         public static void main(String[] args) {
   
5.                 int n= 10, m = 3, i, s=0;
   
6.                 for (i=2; i<=n; i++)
   
7.                         s=(s+m)%i;
   
8.           System.out.println("The winner is:" + (s+1));
   
9.           }
   
10. }

复制代码

也可以用数组实现啊：

1. mport java.util.Scanner;
   
2. /**
   
3. *使用数组实现约瑟夫环问题
   
4. *由m个人围成一个首尾相连的圈报数。
   
5. *从第一个人开始，从1开始报数，报到n的人出圈，
   
6. *剩下的人继续从1开始报数，直到所有的人都出圈为止。
   
7. *对于给定的m和n，求出所有人的出圈顺序.
   
8. */
   
9. public class RingTest{
   
10.     public static void main(String[] args){
    
11.         System.out.println("程序说明如下：");
    
12.         System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");
    
13.         
    
14.         //提示输入总人数
    
15.         System.out.println("请输入做这个游戏的总人数：");
    
16.         Scanner sca=new Scanner(System.in);
    
17.         int m=sca.nextInt();
    
18.         //提示输入要出圈的数值
    
19.         System.out.println("请输入要出圈的数值：");        
    
20.         int n=sca.nextInt();
    
21.         System.out.println("按出圈的次序输出序号：");        
    
22.         //创建有m个值的数组
    
23.         int[] a=new int[m];
    
24.         //初始长度，以后出圈一个，长度就减一
    
25.         int len=m;
    
26.         //给数组赋值
    
27.         for(int i=0;i<a.length;i++)
    
28.             a[i]=i+1;
    
29.         //i为元素下表，j代表当前要报的数
    
30.         int i=0;
    
31.         int j=1;
    
32.         while(len>0){
    
33.             if(a[i%m]>0){
    
34.                 if(j%n==0){//找到要出圈的人，并把圈中人数减一
    
35.                     System.out.print(a[i%m]+"  ");
    
36.                     a[i%m]=-1;
    
37.                     j=1;
    
38.                     i++;
    
39.                     len--;
    
40.                 }else{
    
41.                     i++;
    
42.                     j++;
    
43.                 }
    
44.             }else{//遇到空位了，就跳到下一位，但j不加一，也就是这个位置没有报数
    
45.                 i++;
    
46.             }
    
47.         }
    
48.     }
    
49. }

复制代码