Josephus环问题

约瑟夫环问题

问题描述：

Josephus问题可以描述为如下的一个游戏：N个人编号从1到N，围坐成一个圆圈，从1号开始传递一个热土豆，经过M次传递后拿着土豆的人离开圈子，由坐在离开的人的后面的人拿起热土豆继续进行游戏，直到圈子只剩下最后一个人。例如：M=0，N=5，则游戏人依次被清除，5号最后留下；如果M=1，N=5，那么被清除的人的顺序是2,4,1,5，最后剩下的是3号。

如下是两种解题方法：

建立一个N大小的数组，存储N个人是否还在圈子内（0为在圈子内，-1为已经离开圈子），依次循环遍历整个数组，直到剩下的人数（left）为1。

  public static void pass(int m, int n){
        int[] num = new int[n];
        int left = n;  //剩下的人数
        int index = 0; //当前遍历到的位置
        while(left != 1){
            for(int i = 0; i< m; i++){
                if(num[index++] != 0)   //如果当前人已经清除
                    i--;
                if(index >= n)
                    index = 0; 
            }
            while(num[index] != 0){
                index++;
                if(index >= n)
                index = 0;
            }
            System.out.println("out number is " + (index + 1));
            num[index] = -1;    //将清除的数据下标置-1
            index++;
            if(index >= n)
                index = 0;
            left--;
        }
    }

第二种方式，将1~N的数添加到一个ArrayList对列中，首先计算偏移量（mPrime），当mPrime小于对列长度的一半时，则从前往后依次遍历找到清除的元素；当mPrime大于对列长度的一半时，从后往前遍历找到清除的元素。

public static void pass2(int m, int n){
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i = 1; i <= n; i++)
            list.add(i);
        ListIterator<Integer> iter = list.listIterator();
        int left = n;    //剩下的人数
        int item = 0;    //the out number
        for(int i= 1; i < n; i++){
            int mPrime = m % left;
            if(mPrime < left/2){     //如果当前的偏移量小于list长度的一半时
                if(iter.hasNext())
                    item = iter.next();
                for(int j = 0; j < mPrime; j++){
                    if(!iter.hasNext())
                        iter= list.listIterator();
                    item = iter.next();
                }
            }
            else{  //当偏移量大于list长度的一半时，从后往前找
                for(int j = 0; j< left - mPrime; j++){
                    if(!iter.hasPrevious())
                        iter = list.listIterator(list.size());
                    item = iter.previous();
                }
            }
            System.out.println("out number is " + item);
            iter.remove();
            if(!iter.hasNext())    //有可能下一次循环mPrime就会小于left的一半
                iter = list.listIterator();
            left--;
        }
    }

总结

当M，N较大时，则第二种方法时间效率更高，实现表明，当N=100000，M=9000时（省略的两个算法中的syso语句），方法一个执行时间是30713ms，而第二种方法的执行时间仅为4891ms，M越大时方法一的时间效率会更差。

Josephus环问题

约瑟夫环问题

问题描述：

如下是两种解题方法：

总结