黑马程序员技术交流社区

标题: 约瑟夫环这个例子还是搞不懂啊 [打印本页]
作者: hei930923    时间: 2016-1-26 19:40
标题: 约瑟夫环这个例子还是搞不懂啊
约瑟夫环这个例子还是搞不懂啊
作者: liuxiaoye    时间: 2016-1-26 20:46
就是第二轮的时候要注意，第一轮的3,6,9都已经不在了，要跳过计数
作者: olivec    时间: 2016-1-28 19:02

public class Test4 {
        private static final int count=6;
        private static final int key=3;
        public static void main(String[] args) {
                int[]arr=new int[count];
                for (int i = 0; i < count; i++) {
                        arr[i]=i+1;
                }
                System.out.println(getPosition(arr, key));
        }

        public static int getPosition(int[]arr, int key){
                int index=0;
                int count=1;
               
                //检查是不是只剩一个元素不是0
                while(check(arr)){
                        //索引越过最后一位时重置为0
                        if(index>arr.length-1){
                                index=0;
                        }
                        //如果当前元素是0则跳过当前元素
                        while(arr[index]==0){
                                index++;
                                if(index>arr.length-1){
                                        index=0;
                                }
                        }
                        //如果是第key个元素就置为0
                        if(count%key==0){
                                arr[index]=0;
                        }
                        index++;
                        count++;
                }
                for (int i : arr) {
                        if(i!=0){
                                return i;
                        }
                }
                return -1;
        }
       
        public static boolean check(int[]arr) {
                int count=0;
                for (int i : arr) {
                        if(i!=0){
                                count++;
                        }
                        if(count>1){
                                return true;
                        }
                }
                return false;
        }
}
作者: yi651312197    时间: 2016-1-28 19:31
这个题目是什么
作者: j6819236    时间: 2016-1-31 18:32
  1. package com.heima;

  3. import java.util.ArrayList;

  5. public class Test7 {
  6.         /*
  7.          * 约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）
  8.          * 围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始
  9.          * 报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
  10.          */
  11.         public static void main(String[] args) {
  12.                 System.out.println(lastOne(1, 3, 8));
  13.         }

  15.         // start代表编号为K，开始数数;end代表m，数到m那个人出列;sum总共有n个人
  16.         public static int lastOne(int start, int end, int sum) {
  17.                 ArrayList<Integer> list = new ArrayList<>();
  18.                 //用集合模拟1,2,3,4..n个人围成一桌
  19.                 for (int i = 1; i <= sum; i++) {
  20.                         list.add(i);
  21.                 }
  22.                 int count = 1;   //数数变量,记录当前已数到哪个数
  23.                 //start-1是因为集合索引从0开始，只要集合不只剩一个人就一直数数剔除人
  24.                 //i记录count数数变量所指的集合位置，也就是数到的人
  25.                 for (int i = start - 1; list.size() != 1; i++) {
  26.                         //数到圆圈中最后一个人，从剩下的第一人也就是集合索引为0的人继续
  27.                         if (i == list.size())
  28.                                 i = 0;
  29.                         /*每数到第end个人数就剔除,i--是因为ArrayList集合底层数组实现，
  30.                         每删除一个元素，后面的元素都会往前移一位，这样不会漏数i后面的第一个元素*/
  31.                         if (count % end == 0)
  32.                                 list.remove(i--);
  33.                         count++; //往后数一个数
  34.                 }
  35.                 return list.get(0);//获取最后剩下一人的编号
  36.         }
  37. }
复制代码




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