当前位置: 安卓之星 -> Java开发 -> Josephus问题的java实现

Josephus问题的java实现

作者:网络 发表于: 2017-02-26 点击: 202 次
import java.util.ArrayList;
import java.util.ListIterator;

public class Josephus {

    public static void main(String[] args) {
        pass(9, 5);
        //注意这里的9为传递次数,要与报数次数区分开.即:传递次数 = 报数次数-1.
    }
    
    public static void pass(int m, int n)
    {
        int i, j, mPrime, numLeft;
        ArrayList<Integer> L = new ArrayList<Integer>();
        //  为队列中的成员编号:从1~n
        for (i=1; i<=n; i++)
            L.add(i);
        //  初始化各个元素
        ListIterator<Integer> iter = L.listIterator();
        Integer item=0;
        numLeft = n;
        mPrime = m % n;
        //  进行n此循环,每次删除一个成员
        for (i=0; i<n; i++)
        {
            mPrime = m % numLeft;
            if (mPrime <= numLeft/2)
            //当mPrime小于剩余人数的一般时,进行正移。(向后移next)
            {
                if (iter.hasNext())
                    item = iter.next();
                for (j=0; j<mPrime; j++)
                {
                    if (!iter.hasNext())
                    iter = L.listIterator();
                    item = iter.next();
                }
            }
            else
            {
                for (j=0; j<numLeft-mPrime; j++)
                // 当mPrime大于剩余的一般人数时,进行反移。(向前移previous)  
                {
                    if (!iter.hasPrevious())
                        iter = L.listIterator(L.size());
                    item = iter.previous();
                }
            }
            System.out.print("Removed " + item + " ");
            iter.remove();
            if (!iter.hasNext())
            iter = L.listIterator();
            System.out.println();
            for (Integer x:L)  // 利用增强for循环遍历表
            System.out.print(x + " ");
            System.out.println();
            numLeft--;
        }
        System.out.println();
        }
}

对于Josephus问题有两个地方是可以进行优化的。 (总人数为N,编号为从0~N-1;经过M次报数去除一个成员,剩余成员个数为numleft, 记M%numleft为mPrime)
1、被移除的成员离上一个成员之间的距离是M%numleft-1(报数次为M%numleft).当M大于N时,该计算方式将节省大量时间
2、当mPrime大于numleft的时候可以反向遍历该表来查找要去除的成员。这样可以节省时间。同样这也就要求了该表必须是一个双向表才行。(即含有Previous方法)

该算法实现原理即为:

第一轮,必定为编号M%N-1的成员被去除,第二轮为在第一轮的基础上即从编号为M%N的成员开始正移mPrime-1个单位(或者反移numleft-mPrime-1个单位)。若将M%N即为编号0,开始重新编号,那么第二轮被删除的成员编号便是M%(numleft)-1,由此可得该轮要被删除的成员与上一轮去除成员之间的距离为M%numleft,这里可利用迭代器来实现。

  这里我们便可以得到成员编号与该轮成员数目的关系是:(n表示该轮所剩余的成员数目,Index(n)表示该轮成员的编号(从0开始))
   Index(n) = (Index(n – 1) + m) % n。

相关文章

相关文章

赶快留言冒泡

  • 评论 (0)
  • 引用通告 (0)
目前还没有任何评论.
目前还没有任何Trackbacks和Pingbacks.
吐个泡浮上去.