Josephus问题的java实现

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问题的不同实现方法与总结

上一篇:tomcat启动项目内存溢出问题


下一篇:java运算