A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 郑阳阳 中级黑马   /  2014-7-30 17:35  /  936 人查看  /  10 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

/*有100个人围成一个圈,从1开始报数,报到14的这个人就要退出。然后其他人重新开始,
从1报数,到14退出。问:最后剩下的是100人中的第几个人?*/
class mathPerson
{
        public static void main(String[] args)
        {
                //用来存储编号
                int[] a = new int[101];
                //用来计数到14的
                int j = 0;
                //用来计算还有多少个编号
                int count = 0;
                for(int i=1;i<=100;i++)
                {
                        a[i] = i;
                }
                while(true)
                {
                        j++;
                        if(j%14==0)
                        {
                                //判断还有多少个编号
                                for(int n=1;n<101;n++)
                                {
                                        if(a[n]!=0)
                                        {
                                                count++;
                                        }
                                }
                                //当只剩下一个编号的时候结束循环
                                if(count==1)
                                {
                                        break;
                                }
                                //判断要退出的编号是否是0;代表是否存在,如果不为0代表存在,去除它就将它值为0;
                                if(a[j-((j-1)/100)*100]!=0)
                                {
                                        a[j-((j-1)/100)*100] = 0;
                                }
                                //如果编号不存在就往下找
                                else
                                {
                                        for(int m=1;m<=100;m++)
                                        {
                                                if(a[(j-((j-1)/100)*100+m)/100*100]!=0)
                                                {
                                                        a[(j-((j-1)/100)*100+m)/100*100] = 0;
                                                }
                                        }
                                }
                                       
                        }
                }
                //遍历打印剩下的唯一编号
                for(int s=1;s<101;s++)
                {
                        if(a[s]!=0)
                                System.out.println(a[s]);
                }
        }
}
报告异常真心的没检测出来 啊 都一下午了

10 个回复

倒序浏览
这题好难,真佩服你
回复 使用道具 举报
一开始我也用数组来做,发现太麻烦,而且想到,如果玩的人太多,只是改一下状态,而不是把人踢出列队的话,如果每次都判断那个人是否已经被去除的话,到后面会有很多无谓的判断,就改用ArrayList,这个可以移去元素。
回复 使用道具 举报
本帖最后由 cheye0207 于 2014-7-31 04:02 编辑

感觉是挺难的。。
回复 使用道具 举报
看了你的代码,有几个问题。感觉你应该改下代码习惯。我也没有重写,就在你上面改的。
尽量把各种方法单独封装,你这主函数有点胖!
先说下运算的结果:最后留下的是原来人群中序号为1的人
由于我在这里插代码,几次都是乱码,可惜。
为了求证我的正确,只能“来个有图有真相”。问题在下面指出,并附上运算结果截图。








回复 使用道具 举报
黎志勇 发表于 2014-7-30 17:43
一开始我也用数组来做,发现太麻烦,而且想到,如果玩的人太多,只是改一下状态,而不是把人踢出列队的话, ...

不是只改状态吗?怎么还用ArrayList去移去元素。
回复 使用道具 举报
  1. import java.util.*;
  2. public class Test10
  3.         {
  4.         public static void main(String[] args)
  5.                 {
  6.                 ArrayList<Integer> al = new ArrayList<Integer>();//新建一个集合,用于存储这100个人
  7.                 for(int i = 1; i<=100; i++)//给集合添加元素
  8.                         al.add(i);//添加到集合
  9.                 ArrayList<Integer> newAl = new ArrayList<Integer>();//新建一个集合,用于存储每次退出的那个人
  10.                 newAl = getQuit();//通过调用getQuit()方法,给集合添加元素
  11.                 al.removeAll(newAl);//所有人的集合减去退出的集合,就获得最后剩下没有退出的那13个人
  12.                 System.out.println("最后剩下的人是:");
  13.                 for(Iterator<Integer> it = al.iterator(); it.hasNext();){//迭代取出集合的元素
  14.                         System.out.println("第"+it.next()+"个人");//打印集合的元素
  15.                 }
  16.         }
  17.         private static ArrayList<Integer> getQuit() //创建一个方法,用于获取每次退出的那个人的角标
  18.                 {
  19.                 ArrayList<Integer> newAl = new ArrayList<Integer>();//新建一个集合,用于存储退出的角标
  20.                 int count = 0;//定义一个计数器,记录数数的值
  21.                 //因为是一个圆圈,假定把这个圆圈拉直,把N个这样的直线连起来,就相当于永远在圆圈转圈。
  22.                 for(int i = 1; i<101; i++)//因为有100人,定义一个循环次数为100的循环,i为每个人的角标
  23.                         {
  24.                         count++;//记录索引值
  25.                         while(newAl.contains(i))//判断集合是否已经添加了i
  26.                                 {
  27.                                 i++;//如果集合中已有那个元素,就往后加一个,再判断,直到集合中没有那个元素结束
  28.                                 if(i==101)//如果是第100个人的话,就从1开始
  29.                                         {
  30.                                         i = 1;
  31.                                         }
  32.                                 }
  33.                         if(count%14==0)//如果计数器数到14,就将i添加到集合
  34.                                 {
  35.                                 newAl.add(i);//把这个元素加到集合去
  36.                                 count = 0;//把计数器置0;重新计数
  37.                                 }
  38.                         if(i==100)//当数到第100个人的时候
  39.                                 {
  40.                                 i=1;//把索引置为1,1开始接着数。
  41.                                 }
  42.                         if(newAl.size()>86)//循环终止条件:当圈子中剩余13个元素,也就是集合里面已经添加了87个就退出循环
  43.                                 break;//退出循环
  44.                 }
  45.                 return newAl;//返回newAl
  46.         }
  47. }
复制代码
这个就是用的Arraylist做的,我昨天刚做了这道题,所以比较有印象.
回复 使用道具 举报
本帖最后由 黎志勇 于 2014-7-31 10:55 编辑
a6511631 发表于 2014-7-31 09:17
不是只改状态吗?怎么还用ArrayList去移去元素。

ArrayList容易点呗,想想如果有10000个人在玩,玩到后面剩下100人,如果只改状态的话,后面不是都要去判断那已经被更改为“出列”状态的9900人么,这些判断效率很低吧。
  1. package test;

  2. import java.util.ArrayList;
  3. import java.util.List;

  4. public class Test6 {
  5.         public static void main(String[] args) {
  6.                 game(100,14);
  7.         }
  8.        
  9.         public static void game(int person,int num){
  10.                 System.out.println(person+"人开始游戏");
  11.                 List<Integer> list = new ArrayList<>();
  12.                 for (int i = 1; i <= person; i++) {
  13.                         list.add(i);//构造列队
  14.                 }
  15.                 int count = 0;//下一个要数的数字,因为没开始,初始化为0
  16.                 int pos = -1;//当前列队中,下一个要报数的人在列队中的位置,首编号为0,因为还没开始,初始化为-1
  17.                 while (list.size()>1) {
  18.                         //确定这次要报的数字
  19.                         if (count==num) {
  20.                                 count = 1;
  21.                         } else {
  22.                                 count++;
  23.                         }
  24.                         //确定要报数的人在列队中的位置
  25.                         if (pos==list.size()-1) {
  26.                                 pos = 0;
  27.                         } else {
  28.                                 pos++;
  29.                         }
  30.                         System.out.println(list.get(pos)+"号在数"+count);//报数
  31.                         if(count == num){
  32.                                 System.out.println("---------"+list.get(pos)+"数到"+count+",被踢出去");
  33.                                 list.remove(pos);
  34.                                 pos--;//因为数到14的人被踢出去,下一个会将这个位置补上,这个位置要再利用一次,所以减1回滚
  35.                         }
  36.                 }
  37.                 System.out.println("游戏结束,剩下的是"+list.get(0));
  38.         }
  39. }
复制代码


回复 使用道具 举报
在这里同问
回复 使用道具 举报
黎志勇 发表于 2014-7-31 10:48
ArrayList容易点呗,想想如果有10000个人在玩,玩到后面剩下100人,如果只改状态的话,后面不是都要去判 ...

ArrayList在中间删元素效率也挺坑爹,环状链表会好一点。当然要是真有10000人,我还是去找递推公式吧
回复 使用道具 举报
入学考试就做的这题,100个人报14条件下,用集合和Iterator写很清爽啊。=,=不过数字大了很慢。
就是取一个人报一个数,到14就remove,到结尾就重新返回迭代器继续报
  1. public class Test10 {
  2.         public static void main(String[] args) {
  3.                 long time = System.currentTimeMillis();
  4.                 int totalNum = 100;                //总人数
  5.                 int keyNum = 14;                //报数周期
  6.                
  7.                 List<Integer> list = new ArrayList<Integer>();                //建立有序集合
  8.                
  9.                 for(int i=1; i<totalNum+1; i++) {                //将100个人按顺序存入集合
  10.                         list.add(i);
  11.                 }
  12.                
  13.                 Iterator<Integer> it = list.iterator();                //获取迭代器
  14.                
  15.                 int currentNum = 0;                        //当前报数
  16.                
  17.                 while(list.size()>1) {                        //当圈内人数大于一个时,循环
  18.                        
  19.                         if(!it.hasNext())                        //如果已到圈尾,则重新获取迭代器,返回圈头继续报数
  20.                                 it = list.iterator();
  21.                        
  22.                         it.next();                        //获取当前报数的人
  23.                         currentNum++;                //获取当前所报的数
  24.                        
  25.                         if((currentNum = currentNum % keyNum ) == 0){                //如果当前所报数为keyNum,则此人出圈,当前报数清零,下一个人从1开始报
  26.                                 it.remove();
  27.                         }
  28.                        
  29.                 }
  30.                
  31.                 System.out.println("最后剩下的是第"+list.get(0)+"个人。");                //打印最后剩下的人。
  32.                 System.out.println(System.currentTimeMillis()-time);
  33.         }
  34. }
复制代码


另外这玩意有成熟解法……可是我头大看不下去。
http://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马