黑马程序员技术交流社区

标题: 求解惑：100人围圈报14的人退出问题？感觉题目没交代清楚... [打印本页]

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

作者: manu_chen 时间: 2014-12-14 22:46
新手的路过。

作者: Rain2692 时间: 2014-12-14 23:09
从猴子选大王开始。。。到习得约瑟夫环的问题，都是一类的题目。。。关注我的帖子，会及时的更新题目和答案！！

作者: lishuliang28 时间: 2014-12-15 12:07
楼主肯定是从第十五个人开始报一

作者: 芭芭拉2 时间: 2014-12-15 14:14

lishuliang28 发表于 2014-12-15 12:07
楼主肯定是从第十五个人开始报一

恩恩，肯定是这样。要不然这题没法做吧。。谢咯。。。

作者: SpiderManZZH 时间: 2014-12-15 16:47
哥们，你幸运了，我最晚熬夜把这道题搞通了，下面是分析和代码。
有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);
}
}

作者: shuoshuo 时间: 2014-12-15 18:51
新手进来看看

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

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