就是100个人围成一圈 报到14就退出 问最后剩下的是第几个人的那道题 我的方法是这样的

1. /**
   
2. * 10、 有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
   
3. *
   
4. * @author GP
   
5. *
   
6. */
   
7. public class Test10 {
   
8. 
   
9.         private static final int amount = 100;//总人数
   
10.         private static final int shift = 14;//点名数
    
11. 
    
12.         public static void main(String[] args) {
    
13. 
    
14.                 List<Integer> list = new ArrayList<Integer>();
    
15.                 int i = 0;
    
16.                 while (i++ < amount) {
    
17.                         list.add(i);//将1到100存入集合
    
18.                 }
    
19. 
    
20.                 method(list);
    
21. 
    
22.                 System.out.println("最后剩下的是第" + list.get(0) + "个人");
    
23. 
    
24.         }
    
25. 
    
26.         private static void method(List<Integer> list) {
    
27. 
    
28.                 int count;//用来记录剩下的人数
    
29.                 int pos = 0;//退出的位置
    
30. 
    
31.                 while ((count = list.size()) > 1) {
    
32.                         for (int i = 0; i < shift - 1; i++) {//报数的偏移量是14-1
    
33.                                 pos++;//每报数一次 偏移量增加1
    
34.                                 /*
    
35.                                  * 判断
    
36.                                  * 如果pos等于count 证明已经报到最后一个人的下一个 也就是又从头开始 所以这时将pos置为0
    
37.                                  * pos只有一种情况会大于count 即当某次循环结束时 pos比count小1 但是下面的remove方法将删除了list中的一个元素
    
38.                                  * 这样下一次循环开始时pos和count就是相等的 pos++后 pos就大于count 且只可能大1
    
39.                                  * 所以这样写判断
    
40.                                  */
    
41.                                 if (pos >= count) {
    
42.                                         pos = pos - count;
    
43.                                 }
    
44.                         }
    
45.                         list.remove(pos);//将报14的人删掉
    
46.                 }
    
47. 
    
48.         }
    
49. }

复制代码

可是我看到贴吧里有人这样做 连集合都没用 几行代码就解决了 但是小弟不才 死活没看懂这个思路 召唤大神 来给讲讲思路！

1. int N = 100;
   
2. int s = 0;
   
3. int m = 14;
   
4. for(int i=2; i<=N; i++) {
   
5. s = (s+m)%i;
   
6. }
   
7. System.out.println("最终会留下的人的编号为:" + (s+1));

复制代码

两段代码的结果是一样的 但是下面这个我真是没看懂 有人知道思路吗 给讲讲呗 {:2_31:}

由题目可以知道 循环99次 所以那个循环是99次
而为什么 i=2 呢？
因为 是最后出去的一个人一定是2个中的一个 然后 i++
就是逆向求出环的出去的人的数字 用 s 保存
s开始是0 是 数据计算的模型的开始
数学模型是 0~n-1的问题 这样就比较好算了 因为最后的偏移量是1的话会无法进行数学运算的

设： 上次出局人是 x  偏移量是 p 当前总人数是 n 则下一个出局者就是 y=(x+p)%n
这个是正常的算法 然后是 逆推理
设 ： 本次出局人是 x 偏移量是p 上次总人数是n 则上次出局人就是讲x 与 y 调换位置
x = (y+p)%n
设： x是最后一个留下的人 出上一个人的位置y 关系为
x = (y+p)%2
设： x是倒数第二个人 上一个人的位置y  关系为
x = (y+p)%3
设：已知 当前出局人位置 y 出局人数和 n 偏移量p 求 O 次后的出局人位置
while( O-1） //因为x就是循环之后的位置 所以进行O-1次循环就是O次循环之后的
{
  x = (y+p)%n // x 就是这次的出局位置 然后是再次赋值
  y = x;
n = n+1;
}
最后x的值就是 y 循环 O 次以后的值

由于编程语言的特殊赋值性 可以这样写
while( O-1） //因为x就是循环之后的位置 所以进行O-1次循环就是O次循环之后的
{
  y = (y+p)%n++     // y 就是这次的出局位置 然后是再次赋值
}
然后将 n ++ 提取到 for循环
for( ; 循环O-1次；n++）
y = (y+p)%n
然后因为是第二次开始
for( n=2; 循环O-1次；n++）
y = (y+p)%n
然后控制循环99次
for( n=2; n经过99次循环；n++）
y = (y+p)%n

for( n=2; n<101；n++）
y = (y+p)%n

Etby 发表于 2015-3-24 19:52
由题目可以知道 循环99次 所以那个循环是99次
而为什么 i=2 呢？
因为 是最后出去的一个人一定是2个中的一 ...

为什么是根据取模来进行运算呢？

殷俊 发表于 2015-3-25 11:47
为什么是根据取模来进行运算呢？

我不知道
不过如果是算法的话，先总结出各个要素之间的关系 然后讨论改变
这样的话，是正常的做题思路吧

集合挺好的。可读性强

不错，顶一个

先马一个