黑马程序员技术交流社区

标题: 测试题，100个人报数 [打印本页]

---

作者: zhu_zhu    时间: 2014-9-18 23:40
标题: 测试题，100个人报数
        有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
测试题已经交了，想和大家请教下答案。我感觉我把这道题想简单了呢。还望大神指点

---

作者: dreamseekerkun    时间: 2014-9-19 00:33


我入学测试也抽到了这个题，100个人最后剩下14个人时，第14个就是结果，定义一个集合存储100个数，定义一个循环while(true)，同时定义一个计数器count，里面不断遍历这个集合
当count加到14时，同时也是遍历到的第14个数字，就用迭代器的remove方法删除，remove可以删除最后返回的一个元素同时把count归0
不断循环，直到集合中元素个数为14时，跳出循环，最后一个就是答案
这是我做的
public class Test10 {
        public static void main(String[] args) {
                //定义一个ArrayList集合用来存储数值
                ArrayList<Integer> list = new ArrayList<Integer>();
                //默认添加100个数值
                for (int i = 0; i < 100; i++)
                {
                        list.add(i + 1);
                }
                getnum(list);        
        }
        public static void getnum(List<Integer> list) {
                //定义一个计数器
                int count = 0;
                //只要List集合中元素的个数不等于14，就一直循环
                label: while (true)
                {
                        //迭代器遍历集合
                        Iterator<Integer> it = list.iterator();
                        while (it.hasNext())
                        {
                                int i = it.next();
                                count++;
                                //当count数到14时就把对应那个元素删除
                                if (count == 14)
                                {
                                        //当集合中元素个数等于14时，跳出循环，迭代的最后一个元素就是最后那个数到14的人
                                        if (list.size() == 14)
                                        {
                                                //count计数器等于14并且集合中元素个数有等于14，取出这最后一个元素
                                                System.out.println(list.get(count-1));
                                                //把这个最后数到14的人删除
                                                it.remove();
                                                break label;
                                        }
                                        else
                                        {
                                                //迭代器的remove方法可以删除返回的最后一个元素
                                                it.remove();
                                                //当count=14时，就把count置于0，重新开始计数
                                                count = 0;
                                        }
                                }
                        }
                }
        }
}

---

作者: 谢建平    时间: 2014-9-19 01:56
这个就是最后剩下两个人也能继续报数的   

---

作者: 谢建平    时间: 2014-9-19 03:50

1. 
   
2. public class Test_02 {
   
3. 
   
4.         /**100人围一圈  轮流报数 数到14退 问最后一人在原来的哪个 位置
   
5.          * @param args
   
6.          *
   
7.          * 思路：把这当成100长度数组 不停遍历   轮到9时 数组这位置换一个值  标记下  直到最后一个没标记
   
8.          *                 的再退出
   
9.          */
   
10.         public static void main(String[] args)
    
11.         {
    
12.                         // TODO Auto-generated method stub
    
13.                 int m = 100;
    
14.                 int n = 14 ;
    
15.                        
    
16.                 int index = where(m,n)+1;
    
17.                
    
18.                        
    
19.                 System.out.println(index);
    
20.         }
    
21. 
    
22.        
    
23.        
    
24.         public static int where(int m, int n)        
    
25.         {                //定义一个长度为m的字数，默认全是false
    
26.                 boolean[] bool = new boolean[m];
    
27.                         //定义还剩下的人数
    
28.                 int i = m;        
    
29.                         //每次报计数
    
30.                 int j = 0;
    
31.                         //循环判断  如果只剩下最后一个退出
    
32.                 while(i!=1)
    
33.                 {        // 累加 ， 当加到n时  计数清0  值改为true  累加时值为true不加
    
34.                         for(int k=0;k<bool.length;k++)
    
35.                         {
    
36.                                 if(bool[k]==true) continue;
    
37.                                 j++;
    
38.                                 if(j==n)
    
39.                                 {
    
40.                                         j=0;
    
41.                                         bool[k]=true;
    
42.                                         i--;
    
43.                                 }
    
44.                         }
    
45.                 }
    
46.                         //遍历 查哪个位置还是false 返回
    
47.                 for(int k=0 ;k<bool.length;k++)
    
48.                 {
    
49.                        
    
50.                         if(bool[k]==false)
    
51.                         {
    
52.                                 return k;
    
53.                         }
    
54.                 }
    
55.                         return 0;
    
56.         }
    
57. 
    
58. }
    

复制代码

---

作者: 段金福    时间: 2014-9-19 07:29
第92个，

---

作者: zhu_zhu    时间: 2014-9-19 08:11

dreamseekerkun 发表于 2014-9-19 00:33
我入学测试也抽到了这个题，100个人最后剩下14个人时，第14个就是结果，定义一个集合存储100个数，定义一个 ...

也就是说，退出一个之后是从下一个人重新开始是吧。。

---

作者: zhu_zhu    时间: 2014-9-19 08:14

zhu_zhu 发表于 2014-9-19 08:11
也就是说，退出一个之后是从下一个人重新开始是吧。。

。。。怎么换不了行，不小心提交了。   谢谢指点，醍醐灌顶啊，果然是我考虑的简单了，没想到用count计算，，，完全用的下标。。。。

---

作者: zhu_zhu    时间: 2014-9-19 08:16

dreamseekerkun 发表于 2014-9-19 00:33
我入学测试也抽到了这个题，100个人最后剩下14个人时，第14个就是结果，定义一个集合存储100个数，定义一个 ...

。。。怎么换不了行，不小心提交了。   谢谢指点，醍醐灌顶啊，果然是我考虑的简单了，没想到用count计算，，，完全用的下标。。。。

---

作者: zhu_zhu    时间: 2014-9-19 08:17

段金福 发表于 2014-9-19 07:29
第92个，

我答案错的太离谱了，，，，，，，伤心，，

---

作者: zhu_zhu    时间: 2014-9-19 09:04

谢建平 发表于 2014-9-19 03:50

感谢指点！这个代码的一般性太强了，要思考一会

---

作者: 谢建平    时间: 2014-9-19 09:11
         **** 思路：把这当成100长度数组 不停遍历   轮到9时 数组这位置换一个值  标记下  直到最后一个没标记

这地方先说下哈  是轮到14时 数组这位置换一个值做标记  开始随便用9测的  后来发的时候没注意 没改回来

其实就是数到14的时候 标记  下次数的时候直接跳过这个数接着轮流报数

---

作者: 李天富    时间: 2014-9-19 11:34


约瑟夫环吧。

1. /*
   
2. 思路：新建一个长度为100的数组，然后不断遍历，并用temp记录空值位，
   
3. 每当temp==14的时候，将该位赋值为1（或非空的其他值，就是做个标记），
   
4. 同时用count记录数组中值为1的个数，并将temp清零，当count==99的时候，
   
5. 也就是数组中只剩下一个空值位时停止遍历。最后遍历一次数组，找到空值位
   
6. 的角标x，并返回x+1（因为数组是从0开始编号，所以要加1）.
   
7. 
   
8. 
   
9. 
   
10. 
    
11. 
    
12. 
    
13. */
    
14. 
    
15. 
    
16. 
    
17. class  Joseph
    
18. {
    
19.         public static void main(String[] args)
    
20.         {
    
21.                 int x=Joseph(100,14);
    
22.                
    
23.                 System.out.println("x="+x);
    
24.         }
    
25.         public static int Joseph(int n,int k)
    
26.         {
    
27.                 int[] a=new int[n];
    
28.                 int count=0,temp=0,x=0;//count:记录数组中值为1的元素个数，temp:记录遍历到的空值的个数
    
29.                 while (count<n-1)//不断遍历，只到数组中只剩一个空值位。
    
30.                 {
    
31.                         for (int i=0;i<a.length ; i++)
    
32.                         {
    
33.                                 if(a[i]!=1)//因为数组默认初始化值为空，所以不等于1就是表示空位。
    
34.                                         temp++;
    
35.                                 if(temp==k)
    
36.                                 {
    
37.                                         a[i]=1;
    
38.                                         count++;
    
39.                                         temp=0;
    
40.                                 }
    
41.                                        
    
42. 
    
43.                         }
    
44.                 }
    
45.                 for (int i=0;i<a.length ;i++ )//最后一次遍历，获取剩余最后一个空值位的角标。
    
46.                 {
    
47.                         if (a[i]!=1)
    
48.                         {
    
49.                                 x=i;
    
50.                                 break;
    
51.                         }
    
52.                         
    
53. 
    
54.                 }
    
55.                 return x+1;
    
56.         }
    
57. }
    

复制代码

---

作者: zhu_zhu    时间: 2014-9-27 17:06
我怎么觉得92是最后一个移出去的人呢？

---

作者: cs8630323    时间: 2014-9-28 00:55

李天富 发表于 2014-9-19 11:34
约瑟夫环吧。

1. class aaa
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                 int N = 100;
   
6. int s = 0;
   
7. int m = 14;
   
8. for(int i=2; i<=N; i++) {
   
9. s = (s+m)%i;
   
10. System.out.println(s);
    
11. }
    
12. System.out.println("最终会留下的人的编号为:" + (s+1));
    
13. 
    
14.         }
    
15. }

复制代码

网上找到的最简算法，不知道什么思路

---

作者: fantacyleo    时间: 2014-9-28 01:15
来看看我写的：约瑟夫环问题全攻略http://bbs.itheima.com/thread-144249-1-1.html

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2