ArrayList解100人报数，答案是92吗？请大家帮看下。
============
我的代码。

1. package CollectionFrame;
   
2. 
   
3. import java.util.ArrayList;
   
4. import java.util.Iterator;
   
5. 
   
6. //100个人报数，用ArrayList尝试实现
   
7. public class JerryTest {
   
8. 
   
9.         public static void main(String[] args) {
   
10.                 JerryList jl = new JerryList();
    
11.                 ArrayList<Integer> result = jl.baoshu();
    
12.                 System.out.println("最后一个数是: " +result);
    
13.         }
    
14. }
    
15. class JerryList
    
16. {
    
17.         public ArrayList<Integer> al = new ArrayList<Integer>();  //有点偷懒就写成public了
    
18.         public JerryList()  //构造函数初始化一个size为100 ， 从1到100的AL
    
19.         {
    
20.                 createAL();
    
21.         }
    
22.         private void createAL()
    
23.         {
    
24.                 for(int i=1 ;i<=100;i++ )
    
25.                 {
    
26.                         al.add(i);
    
27.                 }       
    
28.         }
    
29.         public ArrayList<Integer> baoshu() // 主要的实现在baoshu（）方法中
    
30.         {
    
31.                 int count = 0;                                //计数器
    
32.                 System.out.println("原List长度:"+al.size()); //打印下初始的长度
    
33.                         for(Iterator<Integer> it = al.iterator();al.size()!=1 ;)
    
34.                                 /*最核心的思路：
    
35.                                 1.报数其实就是迭代器，每到14就将元素remove ，这时候size会减1，直到只剩一个
    
36.                                 元素时循环结束，所以是al.size()!=1
    
37.                                 2.通过读题，我们知道人是围成圈的，也就是说最后一个元素结束后，指针应该回到整个集合开始的位置
    
38.                                 尝试性的重置了迭代器，没想到还真行～～ it= al.iterator
    
39.                                 3. 返回集合，此时集合中只有一个元素了，就是我们要的答案，我得出的是92 ，不确定是对的。*/
    
40.                         {
    
41.                                 Integer deleteNum = it.next();
    
42.                                 //System.out.println(n);
    
43.                                 count++;
    
44.                                 if(count==14)
    
45.                                 {
    
46.                                         count=0;
    
47.                                         it.remove();
    
48.                                         System.out.println(deleteNum);
    
49.                                 }
    
50.                                
    
51.                                 if(!it.hasNext())       //判断，如果已经到最后一个元素，那么就重置迭代器，形成了环形的集合。
    
52.                                 {
    
53.                                         it=al.iterator();
    
54.                                 }
    
55.                         }
    
56.                         return al;
    
57.         }
    
58. }

复制代码

最核心的思路：
                                1.报数其实就是迭代器，每到14就将元素remove ，这时候集合size会减1，直到只剩一个
                                元素时循环结束，所以是al.size()!=1
                                2.通过读题，我们知道人是围成圈的，也就是说最后一个元素结束后，指针应该回到整个集合开始的位置
                                尝试性的重置了迭代器，没想到还真行～～ it= al.iterator  ， 成功完成了一个环状的集合。
                                3. 返回集合，此时集合中只有一个元素了，就是我们要的答案，我得出的是92 ，不确定是对的。

请大家帮我分析下这样可以吗，有什么地方需要改或者优化的。谢谢了。

结果是对的～ 但是不知道过程是不是可以。

我这样写的。

1. import java.util.LinkedList;
   
2. import java.util.List;
   
3. 
   
4. public class Test4 {
   
5.         public static void main(String[] args) {
   
6.                 game(100, 14);
   
7.         }
   
8. 
   
9.         public static void game(int person, int num) {
   
10.                 List<Integer> list = new LinkedList<Integer>();
    
11.                 for (int i = 1; i <= person; i++) {
    
12.                         list.add(i);
    
13.                 }
    
14.                 int pos = 0;
    
15.                 while (list.size() > 1) {
    
16.                         pos = (pos + num - 1) % list.size();
    
17.                         list.remove(pos);
    
18. 
    
19.                 }
    
20.                 System.out.println(person + "人玩数" + num +
    
21.                                 "，最后剩下的是第" + list.get(0) + "人");
    
22.         }
    
23. }
    

复制代码

黎志勇 发表于 2014-9-19 18:27
我这样写的。

能稍微解释下吗？ 多谢

有更简单的解法，不用任何复杂的数据结构：

1. public int josephusRing(int n,int m) {
   
2.        int k = 0;
   
3.        for(int i = 1;i <= n; i++)
   
4.             k = (k + m - 1) % i + 1;
   
5.        return k;
   
6. }

复制代码

楼上的 简化了代码！

fantacyleo 发表于 2014-9-19 21:35
有更简单的解法，不用任何复杂的数据结构：

请教下具体的过程，不太明白～～

JerryJava 发表于 2014-9-19 21:58
请教下具体的过程，不太明白～～

好，一会儿我干脆专门开个帖子说说这约瑟夫环的问题好了

fantacyleo 发表于 2014-9-19 22:05
好，一会儿我干脆专门开个帖子说说这约瑟夫环的问题好了

大神给力！ 谢过！

JerryJava 发表于 2014-9-20 07:11
大神给力！ 谢过！

完工：http://bbs.itheima.com/thread-144249-1-1.html