黑马程序员技术交流社区

标题: 约瑟夫环通用方法(附带洁癖版本) [打印本页]
作者: 郑飞    时间: 2014-11-21 15:24
标题: 约瑟夫环通用方法(附带洁癖版本)
本帖最后由 郑飞 于 2014-11-24 23:00 编辑

看到N次有人问这个问题 其实在今天之前也觉得难 没试过去做:L 太懒 现在给个通用简洁的方法 希望思路对大家有帮助
  1. class Test
  2. {
  3.         /*
  4.         *定义一个某长度元素值全1的数组1个
  5.         *count不断循环数组并累加所有元素值;
  6.         *count逢3(len)时,元素值改为0(为了下次count访问并累加该元素时不计数,count的存在就是为了逐步把每个元素值都改为0);
  7.         *这时update++(因为count遇到3(len)的倍数了,update记录);
  8.         *当update为arr.length的时候说明找到最后一个元素,返回角标+1;
  9.         **/
  10.         public static void main(String[] args)
  11.         {
  12.                 int[] arr = new int[arr.length];//定义一个长度50,元素值都为1的数组;
  13.                 for(int i = 0;i<50;i++)
  14.                         arr[i] = 1;
  15.                 System.out.println(test(arr,3));//给定数组,和间隔,调用方法;
  16.         }
  17.         public static int test(int[] arr,int len)
  18.         {
  19.                 int result = -1;
  20.                 int temp ;
  21.                 for(int i =0,count = 0,update = 0;update<arr.length;i++)//上面说的很清楚了
  22.                 {
  23.                         if(i==50)//让循环一直持续
  24.                                 i=0;
  25.                         temp = count;//记录上一次的累加结果
  26.                         count+=arr[i];//累加本次访问到的元素的值
  27.                         if(temp%len!=0&&count%len==0)//逢被len整除的元素
  28.                         {
  29.                                 arr[i] = 0;//元素值改为0
  30.                                 update++;//记录次数
  31.                         }
  32.                         result = i+1;//最后一次赋值作为返回值
  33.                     }
  34.                 return result;
  35.         }
  36. }
复制代码


洁癖版本:个人喜好,给自己攒点成就感,提高编程兴趣,娱乐一下;
  1.         public static int test(int[] arr,int len)
  2.         {
  3.                 int result = -1;
  4.                 for(int i =0,count = 0,update = 0;update<arr.length;i++,i = i==arr.length?0:i)
  5.                         if(count%len!=0&(count+=arr[i])%len==0)
  6.                         result = i+1+(arr[i]=(0*update++));
  7.                 return result;
  8.         }
复制代码


作者: 爱学习的小明    时间: 2014-11-21 15:59
学习了，这题有点难度
作者: dong53821713    时间: 2014-11-21 16:17
给力啊 学习 了
作者: wf111sxwf    时间: 2014-11-21 16:42
给大神膜拜了:D
作者: 郑飞    时间: 2014-11-21 17:27
wf111sxwf 发表于 2014-11-21 16:42
给大神膜拜了

呵呵 就是找点感兴趣的 要不整天按部就帮的学感觉好类 别这么说 我想告诉你我好些API都不太熟呢 ;P
作者: chen_32768    时间: 2014-11-21 22:35
大神就是大神，膜拜！！！
作者: 郑飞    时间: 2014-11-21 23:10
chen_32768 发表于 2014-11-21 22:35
大神就是大神，膜拜！！！

正好这个题目很配合 好几个地方可以揉到一起;P
作者: 冥夜    时间: 2014-11-24 19:33
很好，长见识了。不过貌似要考虑下特殊情况人数为1的时候直接输出1.
作者: 郑飞    时间: 2014-11-24 23:15
冥夜 发表于 2014-11-24 19:33
很好，长见识了。不过貌似要考虑下特殊情况人数为1的时候直接输出1.

之前我做的是50长度的 代码中有个地方没改过来 现在改过来了
你说的人数1的时候也可以了:handshake
作者: Evred    时间: 2014-11-25 09:56
来学习了！
作者: 青鱼    时间: 2014-11-25 13:19
赞! 这道题当时花了我半天的时间, 还参考了别人的解法, 才做出来, 泪死了~:'(
作者: nishi5151    时间: 2014-11-25 14:44
学习学习
作者: 農邨尛夥兒    时间: 2014-11-25 17:17
牛人太多了 学习了
作者: qq8921310    时间: 2014-11-25 18:18
有几点不太明白。1）result 为什么要定义为-1.？2）已经有temp=count 了，temp%len!=0&&count%len==0这个判断跟单个的判断有什么区别。
作者: 郑飞    时间: 2014-11-25 22:24
本帖最后由 郑飞 于 2014-11-25 23:03 编辑
qq8921310 发表于 2014-11-25 18:18
有几点不太明白。1）result 为什么要定义为-1.？2）已经有temp=count 了，temp%len!=0&&count%len==0这个判 ...

1.其实result定义成<=0的值都行 因为我们做出的结果肯定是1---arr.length的
2.因为count如果上一次能被整除(已经update++)处理过,紧接着下次可能碰到的元素值为0,累加以后又能被整除,但这个元素其实已经作废; 所以为了杜绝这种情况,我们就判断上一次和本次(上一次不被整除,这一次被整除,才能说明累加进来的是1,)
可能有点绕 希望你能看明白:L
作者: cgsilen    时间: 2014-11-25 22:59
学习了         
作者: 天涯无痕    时间: 2014-11-25 23:29
取经。。。。。
作者: 我是一个小马甲    时间: 2014-11-25 23:29
import java.util.*;
public class Demo2 {
        public static void main(String[] args){
                removePerson(100,14);
        }
        //该方法用来判断pnum个人，报num的退出，最后剩谁，并打印结果
        public static void removePerson(int pnum,int num){
                List<String> list=new ArrayList<String>();
                //定义要删除的元素的下标
                int count=num-1;
                //添加元素
                for(int i=1;i<pnum+1;i++){
                        list.add("第"+i+"人");
                }
                while(list.size()>1){
                        while(count>=list.size()){
                                count=count-list.size();
                        }
                        if(list.size()==1)
                                break;
                        while(count<list.size()){
                                list.remove(count);
                                count=count+num-1;
                        }
                }
                System.out.println("最后剩下的是"+pnum+"人中的"+list);
        }
       
}
----------------------------------------------------------------------------
我写的也分享给大家:D
作者: quick3g    时间: 2014-11-26 01:29
学习了，赞一个。。。
作者: 冬天的雪    时间: 2014-11-26 09:46
学习了，对于查看API文档是很重要的。



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