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。
该算法的详细解析与其他方式的实现可参见文章：