黑马程序员技术交流社区

标题: 100人围圈报数问题，两种方法供参考 [打印本页]
作者: zl074081027_hm    时间: 2015-5-13 11:22
标题: 100人围圈报数问题，两种方法供参考
--------------------------方法一：利用数组-------------------------
直接用数组做，经测试效率最高，10万人时耗时约30ms。
  1. package com.itheima;
  2. /**
  3. * 第10题：有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。
  4. * 然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
  5. * @author zl
  6. *思路：
  7. *一，可以定义一个数组，数组的索引表示每个人的id，元素大小可以设为0和1，0表示数到14的出圈的人，1表示还在圈里；
  8. *二，定义count，表示当前报的数，具有累加性，定义在循环外；num表示在圈里剩下的人数；
  9. *三，定义嵌套循环，内循环表示遍历数组并进行判断剩余的人数；外循环一直执行直到剩余人数为1就跳出。
  10. *四，每次都要遍历完整个数组并进行判断，效率却很高，貌似是最高的。
  11. */
  12. public class Test10CricleCountArray {

  14.         public static void main(String[] args) {
  15.                 long before = System.currentTimeMillis();
  16.                
  17.                 int left = circleCount(100000);
  18.                 System.out.println("剩下的人的序号为："+left);
  19.                
  20.                 long after = System.currentTimeMillis();
  21.                 System.out.println(after-before);//为10000人时，耗时约30ms
  22.         }

  24.         public static int circleCount(int n) {

  26.                 int[] arr = new int[n];
  27.                 for(int i=0; i<arr.length; i++) {
  28.                         arr[i] = 1;//1表示在圈中，0表示出圈
  29.                 }       
  30.                
  31.                 int count = 0;//当前应该报的数
  32.                 int num = arr.length;//剩余人数

  34.                 while(num>1) {
  35.                         num = arr.length;//圈里剩下的人数（假设全部在圈内）；
  36.                        
  37.                         for(int i=0; i<arr.length; i++) {
  38.                                 if(arr[i]==0) {
  39.                                         num --;//当前人已出圈
  40.                                 } else {
  41.                                         count ++;
  42.                                         if(count == 14) {
  43.                                                 arr[i] = 0;
  44.                                                 count =0;
  45.                                                 num --;        //当前人出圈
  46.                                         }
  47.                                 }
  48.                         }               
  49.                        
  50.                 }
  51.                
  52.                 //获取剩下的人的序号
  53.                 int left = 0;
  54.                 for(int i=0; i<arr.length; i++) {
  55.                         if(arr[i] == 1) {
  56.                                 left = i+1; //索引从0开的，序号需加1！
  57.                         }
  58.                 }
  59.                
  60.                 return left;
  61.         }
  62. }
复制代码

--------------------------方法二：利用容器--------------------------
利用LinkedList时，经测试10万人时，耗时约40ms，与数组相当；
利用ArrayList时，经测试10万人时，耗时约400ms，效率最低。
ackage com.itheima;

import java.util.*;

/**
*  第10题：有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。
* 然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
* @author zl
*思路：
*一：利用容器存储和删除人数；
*二：循环，容器长度为1时跳出，返回元素值；
*三：循环中，数数并删除元素。
*/
public class Test10CircleCountLink {

        public static void main(String[] args) {
                long before = System.currentTimeMillis();
                int left = circleCount(100000);
                System.out.println("剩下的人的序号为："+left );
                long after = System.currentTimeMillis();
                System.out.println(after - before);

        }

        private static int circleCount(int n) {
                //定义容器并初始化
                List<Integer> list = new LinkedList<Integer>();//50000人时，耗时约40ms
//                List<Integer> list = new ArrayList<Integer>();//50000人时，耗时400ms
                for(int i=1; i<=n; i++) {
                        list.add(i);
                }
               
                int count = 0;//当前报数
               
                //循环、判断并输出
                while(list.size()>1) {
                        Iterator<Integer> ite = list.listIterator();
                        while(ite.hasNext()) {
                                ite.next();
                                count ++;
                                if(count==14) {
                                        ite.remove();
                                        count = 0;
                                }
                        }
                }
               
                return list.get(0);
        }

}

以上二种方法，仅供参考。若大家有新的做法，欢迎多多交流，呵呵，~:)。
作者: csu050416    时间: 2015-5-13 13:14
很好的思路。赞一个。学习了。
作者: mmakun    时间: 2015-5-13 14:26
不错的一个问题，貌似某公司的考试题
作者: 柒仴、看雲佉    时间: 2015-5-13 22:31
好样的，，
作者: 980595778    时间: 2015-5-13 22:35
以前接触过类似的题目，现在了解了，谢谢
作者: 932773877    时间: 2015-5-13 22:36
ding。。。。。。。。。。。。。。。
作者: bingyu    时间: 2015-5-14 11:32
学习了、、
作者: Mr7952    时间: 2015-5-14 20:01
学习了。。。



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