前两天做的一道考试题，是一道挺经典的算法题

1. package com.itheima;
   
2. /**
   
3. * 10、 有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，
   
4. * 从1报数，到14退出。问：最后剩下的是100人中的第几个人？
   
5. *
   
6. * @author Administrator
   
7. * */
   
8. public class Test10 {
   
9. 
   
10.         public static void main(String[] args) {
    
11. 
    
12.                 // 定义总数
    
13.                 int total = 100;
    
14.                 // 报到即被退出的数字
    
15.                 int div = 14;
    
16.                 // 最后能被留下的人数
    
17.                 int left = 1;
    
18. 
    
19.                 // 定义一个数组，长度即总人数
    
20.                 int[] it = new int[total];
    
21.                 // 遍历数组并为其每一个元素赋值1
    
22.                 for (int i = 0; i < total; i++) {
    
23.                         it[i] = 1;
    
24.                 }
    
25. 
    
26.                 // 定义一个计数器
    
27.                 int count = total;
    
28.                 // 定义一个指针，代表当前被报到的数字
    
29.                 int pointer = 0;
    
30. 
    
31.                 // 循环直到数组中留下left个元素
    
32.                 while (count > left) {
    
33. 
    
34.                         // 在数组中的每一轮循环
    
35.                         for (int j = 0; j < it.length; j++) {
    
36. 
    
37.                                 // 如果数组的值为0，代表其为退出，不为零则指针加一
    
38.                                 if (it[j] != 0) {
    
39.                                         it[j] = ++pointer;
    
40.                                 } else {
    
41.                                         continue;
    
42.                                 }
    
43. 
    
44.                                 // 如果其能被div整除，代表退出
    
45.                                 if (pointer % div == 0) {
    
46.                                         it[j] = 0;
    
47. 
    
48.                                         pointer = 0;
    
49.                                         count--;
    
50.                                         if (count == left) {
    
51.                                                 break;
    
52.                                         }
    
53.                                 }
    
54.                         }
    
55.                 }
    
56.                 // 判断数组中不为零的元素的位置
    
57.                 for (int i = 0; i < total; i++) {
    
58.                         if (it[i] != 0) {
    
59.                                 System.out.println("最后剩下的是其中的第" + (i + 1) + "个人");
    
60.                         }
    
61.                 }
    
62.         }
    
63. }
    

复制代码

确实很经典，我也做到了，开始也没想出来

我觉得用List集合来做更简单，把1~100封装成Integer对象，放进集合
在ListIterator中设置计数器，用remove方法移除第14个数
。。。。不对，我这样会剩13个，我再想想

第一次报到14的人退出了，重新开始是指从第15个人继续报数吗

我发现我是脑残~

你觉得你的代码高效并且简单 吗？时间复杂度O(n2),猴子选大王的问题做过没，这个题目，用C语言就可以直接秒过！！

聪明叉 发表于 2014-12-6 09:31
第一次报到14的人退出了，重新开始是指从第15个人继续报数吗

对从一开始报，不过接着报也没问题，只要是14的倍数就行

sin 发表于 2014-12-6 21:00
对从一开始报，不过接着报也没问题，只要是14的倍数就行

come on!!baby

Rain2692 发表于 2014-12-6 17:37
你觉得你的代码高效并且简单 吗？时间复杂度O(n2),猴子选大王的问题做过没，这个题目，用C语言就可以直接秒 ...

看题目，是经典问题，不是经典答案哦，有好的赶紧拿出来啊，不要只是评论

sin 发表于 2014-12-6 21:02
看题目，是经典问题，不是经典答案哦，有好的赶紧拿出来啊，不要只是评论 ...

加我好友，我就给你！！

sin 发表于 2014-12-6 21:02
看题目，是经典问题，不是经典答案哦，有好的赶紧拿出来啊，不要只是评论 ...

1. import java.util.ArrayList;  
   
2. import java.util.List;  
   
3. import java.util.Scanner;  
   
4.   
   
5. class Count {  
   
6.     public static void main(String[] args) {  
   
7.         Scanner scanner = new Scanner(System.in);  
   
8.         System.out.print("请输入总人数：");  
   
9.         int totalNum = scanner.nextInt();  
   
10.         System.out.print("请输入报数的大小：");  
    
11.         int cycleNum = scanner.nextInt();  
    
12.         yuesefu(totalNum, cycleNum);  
    
13.     }  
    
14.   
    
15.    public static void yuesefu(int totalNum, int countNum) {  
    
16.         // 初始化人数  
    
17.         List<Integer> start = new ArrayList<Integer>();  
    
18.         for (int i = 1; i <= totalNum; i++) {  
    
19.             start.add(i);  
    
20.         }  
    
21.         //从第K个开始计数  
    
22.         int k = 0;  
    
23.         while (start.size() >0) {  
    
24.             k = k + countNum;  
    
25.             //第m人的索引位置  
    
26.             k = k % (start.size()) - 1;  
    
27.            // 判断是否到队尾  
    
28.             if (k < 0) {  
    
29.                 System.out.println(start.get(start.size()-1));  
    
30.                 start.remove(start.size() - 1);  
    
31.                 k = 0;  
    
32.             } else {  
    
33.                 System.out.println(start.get(k));  
    
34.                 start.remove(k);  
    
35.             }  
    
36.         }  
    
37.     }  
    
38. }

复制代码

这个解法很经典

还有更简单的！！