Java实现 Josephus约瑟夫环问题

import Java.util.ArrayList;
import java.util.ListIterator;
import java.util.Scanner;

public class Josephus {

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m, n;
        m = sc.nextInt();
        n = sc.nextInt();
        pass(m, n);    //  注意这里的m为传递次数,要与报数次数区分开.即:传递次数 = 报数次数-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。

该算法的详细解析与其他方式的实现可参见文章:

Josephus问题的不同实现方法与总结

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/92a11767cc3c65dc03c66827db065e68.html