有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。
然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？


下面是我的解决方案，希望看看大家的解决方式，有没有更简单的？互相学习。

1. import java.util.*;
   
2. class test110
   
3. {
   
4.         public static void main(String[] args)
   
5.         {
   
6.                 //定义一个arraylist集合存储元素
   
7.                 ArrayList<Integer> al = new ArrayList<Integer>();
   
8. 
   
9.                         //向集合中添加100个元素（1-100数字）
   
10.                         for(int i=1;i<=100;i++)
    
11.                         {
    
12.                                 al.add(i);
    
13.                         }
    
14.                 method_1(al);
    
15.         }
    
16. 
    
17.         public static void method_1(ArrayList<Integer> al)
    
18.         {
    
19.                 //此处定义一个集合，是为了方便后面删除元素用。
    
20.                 ArrayList<Integer> buf = new ArrayList<Integer>();
    
21.                
    
22.                 //定义一个计数器，记录大家的报数。
    
23.                 int count=0;
    
24. 
    
25.                 //一直循环报数（1-100转完一圈再继续转的意思），删除元素，直到只剩下一个元素
    
26.                 while(true)
    
27.                 {
    
28.                         //判断元素是否为1
    
29.                         if(al.size()>1)
    
30.                         {
    
31.                                 //100个人内部1-14循环报数
    
32.                                 for(int index=0;index<al.size();index++)
    
33.                                 {
    
34.                                         //进入循环一次，计数器+1
    
35.                                         count++;
    
36. 
    
37.                                         //判断判断报的数是否为14的倍数，这里对1-14循环报数稍微做了下转换，应该不难理解
    
38.                                         if(count%14==0)
    
39.                                         {
    
40.                                                 //如果该角标的报数为14的倍数，则将该元素添加到上面定义好的buf集合。
    
41.                                                 buf.add(al.get(index));        
    
42.                                         }
    
43.                                 }
    
44. 
    
45.                                 //一次性删除al集合中包含的buf集合中的元素。
    
46.                                 al.removeAll(buf);
    
47.                                 //清空buf集合
    
48.                                 buf.clear();
    
49.                         }
    
50.                         else
    
51.                                 break;
    
52.                 }
    
53. 
    
54.                 System.out.println(al);
    
55.         }
    
56. }
    

复制代码

1. package test;
   
2. 
   
3. import java.util.ArrayList;
   
4. 
   
5. public class Math {
   
6. 
   
7.         public static void main(String[] args) {
   
8.                
   
9.                 System.out.println(getPerson(100));
   
10.         }
    
11.         
    
12.         public static int getPerson(int count) {
    
13.                
    
14.                 ArrayList<Integer> as = new ArrayList<>(100);
    
15.                 for (int i = 0;i < count;i++) {
    
16.                         as.add(i + 1);
    
17.                 }
    
18. 
    
19.                 return  getNumber(as, 0);
    
20.                
    
21.         }
    
22.         
    
23.         public static int getNumber(ArrayList<Integer> as,int numberEnd) {
    
24.                 for (int i = 0;i < as.size();i++) {
    
25.                         if ((as.get(i) + numberEnd) % 14 == 0) {
    
26.                                 as.remove(i);
    
27.                         }
    
28.                 }
    
29.                
    
30.                 if (as.size() > 1) {
    
31.                         numberEnd += as.get(as.size() - 1);
    
32.                         getNumber(as,numberEnd);
    
33.                 }
    
34.                
    
35.                 return as.get(0);
    
36.         }
    
37. 
    
38.         
    
39.         
    
40. }
    

复制代码

我也增加一种思路,使用递归.

刘家斌 发表于 2014-10-18 21:23
思想差不多，我感觉这样能简单点

时间复杂度多少?

香草芭芙 发表于 2014-10-19 11:41
答案是 92 对吧?

没错，我也是92

答案到底是71  还是 92

逻辑算是看懂了

刘家斌 发表于 2014-10-18 21:23
思想差不多，我感觉这样能简单点

为什么for(int x=0;x<arr.size();x++)不能用for(int x=0;arr.size()!=1;x++)来判断？
                       

不错不错

1. package com.itheima;
   
2. 
   
3. import java.util.ArrayList;
   
4. 
   
5. public class Test1 {
   
6.         public static void main(String[] args) {
   
7.                 // 创建初始长度为100的集合,并添加元素
   
8.                 ArrayList<Integer> al = new ArrayList<Integer>();
   
9.                 for (int x = 1; x <= 100; x++) {
   
10.                         al.add(x);
    
11.                 }
    
12. 
    
13.                 int pos = 13;
    
14.                 while (al.size() != 1) {
    
15.                         while (pos > al.size() - 1) {
    
16.                                 pos = pos - al.size();
    
17.                         }
    
18.                        al.remove(pos);
    
19. 
    
20.                         pos = pos + 13;
    
21.                 }
    
22.                 System.out.println("最后一个数字为：" + al.get(0));//结果是：92
    
23.         }
    
24. }
    

复制代码

以上是我的代码，答案92

1. package com.itheima.test;
   
2. import java.util.*;
   
3. public class Test100
   
4. {
   
5.         public static void main(String[] args)
   
6.         {
   
7.                 // ------------输入学生人数---------------------
   
8.                 int num = 100; //学生人数.
   
9.                 int outNum = 14; //第几个人出局.
   
10.                 // ------------制作列表-------------------------
    
11.                 List<Integer> list = new ArrayList<Integer>();
    
12.                 for (int x = 0; x < num; x++)
    
13.                 {
    
14.                         list.add(x + 1);
    
15.                 }
    
16.                 // --------------------------------------------
    
17.                 int i = method(list, outNum);
    
18.                 System.out.println("第"+i+"人");// 返回答案.
    
19.         }
    
20.         public static int method(List<Integer> list, int outNum)
    
21.         {
    
22.                 int index = -1;
    
23.                 while (list.size() != 1)
    
24.                 {
    
25.                         for (int x = 1; x <= outNum; x++)
    
26.                         {
    
27.                                 index++;
    
28.                                 if (index >= list.size())
    
29.                                 {
    
30.                                         index = 0;
    
31.                                 }
    
32.                         }
    
33.                         list.remove(index);
    
34.                         index--;
    
35.                 }
    
36.                 return list.get(0);
    
37.         }
    
38. }

复制代码

答案是 92 对吧?

随便看看，还不懂。。。。

哈达洋 发表于 2014-10-18 22:20
恩恩，互相学习

这样应该是对的import java.util.*;
class  Demo
{
        public static void main(String[] args)
        {
                ArrayList<Integer>  s=getSimple(100);
                System.out.println(s.get(0));

        }
        public static ArrayList<Integer> getSimple(int max)
        {
                //定义一个数组，装入1到指定的100的所有值
                ArrayList<Integer> arr=new ArrayList<Integer>();
                for(int x=1;x<=max;x++)
                {
                        arr.add(x);
                }
                //定义一个计数器
                int count=0;
                //开始循环，对集合进行遍历
                while(arr.size()>1)
                {
                        //遍历的时候count自加
                        for(ListIterator<Integer> li=arr.listIterator();li.hasNext();)
                        {
                                Integer i=li.next();
                                count++;
                                if(count==14)
                                {
                                        li.remove();
                                        count=0;
                                }
                        }
                        //判断当集合中只有一个元素时返回。
                }
                return arr;
        }
}

哈达洋 发表于 2014-10-18 22:39
你是说调用完arr.remove()后，重新赋值吗？如果是这个的意思话，就没必要，因为arr.remove()后，arr就已经 ...

确实是，是我没理解对。

qq8921310 发表于 2014-10-18 22:32
我觉得第二个 对arr重新赋值一下就可以了。this.arr= arr

你是说调用完arr.remove()后，重新赋值吗？如果是这个的意思话，就没必要，因为arr.remove()后，arr就已经变成删完后的集合了。因为它底层调用的是System.arrayCopy()方法，在 原来的arr上直接修改的，所以不需要重新赋值了。

我觉得第二个 对arr重新赋值一下就可以了。this.arr= arr

刘家斌 发表于 2014-10-18 22:12
这样啊，我在看看，谢谢提醒啊

恩恩，互相学习

哈达洋 发表于 2014-10-18 22:11
嗯恩，是的。

这样啊，我在看看，谢谢提醒啊

刘家斌 发表于 2014-10-18 22:09
你的意思是在for循环里面第一次被删除一个元素，循环里的size就变了吗

嗯恩，是的。

哈达洋 发表于 2014-10-18 22:07
刚刚运行了下你的代码，发现了个小错误。你的第28行代码：arr.remove(x),这句话一执行，arr就变了，那么 ...

你的意思是在for循环里面第一次被删除一个元素，循环里的size就变了吗

刘家斌 发表于 2014-10-18 21:23
思想差不多，我感觉这样能简单点

刚刚运行了下你的代码，发现了个小错误。你的第28行代码：arr.remove(x),这句话一执行，arr就变了，那么它从删除元素角标以后的元数角标也随之变化了，都往前进了1。当再运行到arr.remove(x)时，这里的x还是按原来的角标在删除元素，所以这时候删除的不再是你想要删除的元素。我搞两个集合的目的就这消除这里的问题。你可以再看看。