黑马程序员技术交流社区

标题: 入学考试面试题分析---100个人围成一个圈报数 [打印本页]

---

作者: 王文辉    时间: 2015-7-21 17:28
标题: 入学考试面试题分析---100个人围成一个圈报数


题目：有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
之前在论坛里看过这个题目，很多人给出了自己的分析结果，发现有些人的结果对，但是过程不对，具体来说就每次退出的人不符合规律。
所以自己写了一个，写的不好请见谅，如果有问题，请大家指出，谢谢。

思路：
1，首先需要明确的是：当报到14的人退出后，重新开始时是从退出的人的下一个开始报数，还是从100人中的第一个开始报数？
2，考虑到后者没什么意义（所有在第十三个后面的会先退出），所以认为重新开始是在退出的人的下一个开始报数。
3，创建一个长度为100的boolean数组，boolean数组新建时默认元素都是false
4，退出的人设置对应的boolean数组元素为true，只有为false可以报数
5，循环结束后剩下的为false的元素的角标就是结果
import java.util.LinkedList;
import java.util.List;
import sun.security.util.Length;

public class Test10 {

        //方便修改
        private final static int sum = 100;//总人数
        private final static int num = 14;//用于判断的编号
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                //初始化玩游戏的总人数
                int len = sum;
                //创建boolean数组，默认元素均为false
                boolean[] b_array = new boolean[len];
                //定义一个变量记录当前报的数
                int count = 0;
                //记录上一个退出的人
                int quit = 0;
               
                //每循环一次，便有一个人退出游戏
                while(len>1){
                        //循环获取需要退出的人，并设置boolean数组中对应的元素为true
                        b: for(int i=quit<sum?quit:0;true;i++){
                                if(i>b_array.length-1){//转了一圈，初始化值为0
                                        i=0;
                                }
                                //判断是否已退出
                                if(!b_array){//为false就报数
                                        count++;
                                        if(count == num){//判断获取退出的人
                                                //若退出，设置对应元素为true
                                                b_array = true;
                                                quit = i+1;//+1是因为要从上次退出的人的下一个人开始报数
                                                System.out.println("第"+(quit)+"个人退出游戏");
                                                //重置报的数
                                                count = 0;
                                                //当前玩游戏的人数减一
                                                len--;
                                                //当获取到退出的人就结束循环,提高效率
                                                break b;
                                        }
                                }
                        }
                }
                //游戏结束，boolean数组中为true的元素的角标+1就是所要得到的结果
                for(int i=0;i<b_array.length;i++){
                        if(!b_array){
                                System.out.println("最后剩下来的人是第"+(i+1)+"个人");
                        }
                }
        }

}

---

作者: Wqi    时间: 2015-7-21 18:19
楼主。这是基础班的入学考试题吗？

---

作者: 王文辉    时间: 2015-7-21 18:30

Wqi 发表于 2015-7-21 18:19
楼主。这是基础班的入学考试题吗？

是就业班的

---

作者: s1714534118    时间: 2015-12-27 18:53
谢谢分享！正好需要！

---

作者: q291793758    时间: 2016-8-23 17:55

[Java] 纯文本查看 复制代码

public class testg {

    public static void main(String[] args) {

        int N = 100;

        int s = 0;

        int m = 14;

        for(int i=2; i<=N; i++) {

            s = (s+m)%i;

        }

        System.out.println("最终会留下的人的编号为:" + (s+1));

    }

}

题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
  k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
现在我们把他们的编号做一下转换：

k     --> 0
k+1   --> 1
k+2   --> 2
...
...
k-2   --> n-2
k-1   --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：S=(x+k)%n
网上找的，我也不懂

---

作者: a623562486    时间: 2016-8-23 21:05
这个……这么难呢

---

作者: 菜菜_f9490    时间: 2016-8-23 21:25
楼主这是什么题  入学？

---

作者: 右耳年华i    时间: 2016-8-23 21:28

q291793758 发表于 2016-8-23 17:55
[mw_shl_code=java,true]public class testg {
    public static void main(String[] args) {
        int ...

你好，这个方法能解释一下吗，理论基础是什么  方法很好

---

作者: 右耳年华i    时间: 2016-8-23 21:29

q291793758 发表于 2016-8-23 17:55
[mw_shl_code=java,true]public class testg {
    public static void main(String[] args) {
        int ...

这个方法的理论基础是什么，老烦解释一下

---

作者: 胡eason    时间: 2016-8-23 21:52
加油！加油！加油！加油！

---

作者: li--yong    时间: 2016-8-23 21:53
太难了吧，搞不懂

---

作者: NewsmallWhite    时间: 2016-8-23 21:56
楼主，赞 一个

---

作者: 王宁007    时间: 2016-8-23 23:30

楼主，赞 一个

---

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

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