约瑟夫环问题

问题描述：

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越大时方法一的时间效率会更差。