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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

       原题是这样的:有100个人围成一个圈,从1开始报数,报到14的这个人就要退出。然后其他人重新开始,从1报数,到14退出。问:最后剩下的是100人中的第几个人?
      疑问:报到14的这个人退出。然后其他人重新开始,从1报数??这个重新开始是什么意思?是从第一个人重新开始报1,?还是从第15个人重新开始报1??这题目没说清楚吧?。。。
       真正的约瑟夫环是这样的:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
         那么这样的话,出题人是不是想让我们理解成从退出的那个人的那个人开始报1呢?要不然很容易理解成继续从原来的第1个人开始报1的呀,理解成这样的话没必要考吧。。。
  求大神指导...新手一枚,求解惑。。。

6 个回复

倒序浏览
新手的路过。
回复 使用道具 举报
从猴子选大王开始。。。到习得约瑟夫环的问题,都是一类的题目。。。关注我的帖子,会及时的更新题目和答案!!
回复 使用道具 举报
楼主肯定是从第十五个人开始报一
回复 使用道具 举报
lishuliang28 发表于 2014-12-15 12:07
楼主肯定是从第十五个人开始报一

恩恩,肯定是这样。要不然这题没法做吧。。谢咯。。。
回复 使用道具 举报
哥们,你幸运了,我最晚熬夜把这道题搞通了,下面是分析和代码。
有100个人围成一个圈,从1开始报数,报到14的这个人就要退出。然后其他人重新开始,从1报数,到14退出。
         *                      问:最后剩下的是100人中的第几个人?
         *
         * 思路:
         *                 1,做这道题之前要想通一点的就是因为多人是围成一个圈来报数的,当人数小于14的时候,一样可以在后面的人报数到14然后退出。
         *                 2,该题需要用到List集合中的LinkedList,因为该集合底层数据结果是链表结构,特点是集合中元素是有序的,每个元素对应一个角标。
         *                 3,当删除一个元素时,后面的元素会自动向前移动一位,集合长度也相应减少一位。
         *                 4,在这一题中还有一个重要的规律,请看分析
         *
         * 如题:有100人,从1开始报数,到14的这人退出,后面的人从新开始从1开始报数,将这100人添加到LinkedList集合中,注意元素和角标的变化关系。
         *      假设这100人从第1个到第100个分别拿着1到100的号码,存入到LinkedList的集合中对应角标是0到99;
         *      a,当14拿着号码的人报数时,它的角标为13,因为报数到14,该人退出。 拿着15号码的人角标变为13,且集合长度变为99;
         *      b,往下数,拿着28号码的人,该人角标为26,报数时报到14,该人退出,拿着29号码的人角标变为26,集合长度变为98;
         *      c,再往下数,拿着42号码的人,该人角标为39,因为报数到14,该人退出,拿着43号码的人角标变为39,集合长度变为97;
         *      d,.......
         *      当拿着98号码的人,该人角标为91,因为报数到14,该人退出,拿着99号码的人角标变为91此时集合的长度为93;
         *      下一次是拿着11号码的人,该人角标为11,因为循环报数到14,该人退出,拿着12号码的人角标变为11,集合长度为92;
         *      ....
         *      因为每次当一个人拿着号码报数到14,该人就退出,集合的长度就减少一位,到最后就会剩下一个拿着号码的人了,这个人就是
         *      要找的人。且此时该人的角标为0,可通过get(0)方法获取该人拿着的号码。这个号码就是原来100人中的第几个人表示的数字。
         *
         */
public class Test10 {

        public static void main(String[] args) {
                //调用方法,获取最后是100人中的第几人。
                int num = getNum(100,14);
                System.out.println("最后剩下的是100人中的第"+num+"个人");

        }

        private static int getNum(int person, int num) {
                List<Integer> list = new LinkedList<Integer>(); //定义List集合用于存放1到100的号码
                for (int i = 1; i <= person; i++) {
            list.add(i);
                }
                int pos = 0;                                                                        //定义角标开始变量,应用while循环,根据上面分析的规律,删除报数到14的人,直到只剩一人
        while (list.size() > 1) {
               pos = (pos + num - 1) % list.size();                //角标、集合长度、和报的数的关系表达式
               list.remove(pos);                                                //根据角标删除号码。good
       }
                return list.get(0);
        }
}
回复 使用道具 举报
新手进来看看
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马