A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 王文辉 于 2015-7-21 17:31 编辑

题目:有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)+"个人");
                        }
                }
        }

}

12 个回复

倒序浏览
楼主。这是基础班的入学考试题吗?
回复 使用道具 举报
Wqi 发表于 2015-7-21 18:19
楼主。这是基础班的入学考试题吗?

是就业班的
回复 使用道具 举报
谢谢分享!正好需要!
回复 使用道具 举报
本帖最后由 q291793758 于 2016-8-23 21:36 编辑

[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
网上找的,我也不懂
回复 使用道具 举报
这个……这么难呢
回复 使用道具 举报
楼主这是什么题  入学?
回复 使用道具 举报
q291793758 发表于 2016-8-23 17:55
[mw_shl_code=java,true]public class testg {
    public static void main(String[] args) {
        int ...

你好,这个方法能解释一下吗,理论基础是什么  方法很好
回复 使用道具 举报
q291793758 发表于 2016-8-23 17:55
[mw_shl_code=java,true]public class testg {
    public static void main(String[] args) {
        int ...

这个方法的理论基础是什么,老烦解释一下
回复 使用道具 举报
加油!加油!加油!加油!
回复 使用道具 举报
太难了吧,搞不懂
回复 使用道具 举报
楼主,赞 一个
回复 使用道具 举报

楼主,赞 一个
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马