约瑟夫环问题说的是,n个人围成一圈,从第k个人开始沿着一个方向报数,报到第m个人时,第m个人出列,从紧挨着的下一个人(未出列)开始,求整个环中人的出列顺序。下面是我用java实现的解决方法。
class JosephLoop { //n为环中人数,m为每次报数的人数,k为报数的起始位置0~n-1 int n,m,k; int[] persons; int[] seq; JosephLoop(int n, int k, int m){ this.n = n; this.m = m; this.k = k; persons = new int[n]; seq = new int[n]; } public void showSeq(){ for (int x:seq ) { System.out.print(x+" "); } } public void calcLoop(){ for(int j=0;j<n;j++) { int index=k; for (int i=0; i<m ; index++) { if (persons[index%n]==0) { i++; } } persons[(index-1)%n] = 1; seq[j] = (index-1)%n; k = (index)%n; } } }
class LoopTest { public static void main(String[] args) { JosephLoop jose = new JosephLoop(12,5,4); //n,k,m jose.calcLoop(); jose.showSeq(); } }