哥们,你幸运了,我最晚熬夜把这道题搞通了,下面是分析和代码。
有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);
}
}
|