package com.bupt.syc;import java.util.Iterator;import java.util.LinkedList;import org.junit.Test;public class Josephus {    // 模拟解法    public static int JosephusWinner(int M, int N) throws Exception {        if (N < M) {            throw new Exception("M should smaller than N");        }        int arr[] = new int[N];        for (int i = 0; i < N; i++) {            arr[i] = 1;        }        int cnt = 0, k = 0, j = 0;        int num=-1;        while(cnt<=N-1){            if(arr[k]==1){                j+=arr[k];            }            if(j==M){                arr[k]=0;                cnt++;            }        }        return num;    }    //公式法     //f(1)=0    //f=(f+m)mod i (i>1)    public static int JosephusWinner2(int M ,int N){        int winner=0;        for(int i=2;i<=N;i++){            winner=(winner+M)%i;        }        return winner;    }    public static void JosephusWinner3(int M ,int N){        LinkedList 
     
       linkedList=new LinkedList
      
       ();        for(int i=0;i
       
        1){            Iterator iterator=linkedList.iterator();            while(iterator.hasNext()){                num++;                iterator.next();                if(num==M){                    iterator.remove();                    num=0;                }            }        }        if(linkedList.size()==1){            System.out.println("winner is :"+linkedList.get(0));        }    }    //题目：有N个人围成一圈，每人有一个编号，从编号为1的人开始，每隔M个出圈，按出圈次序排成一列，其编号刚好按顺序从1到M。     //要求：从键盘输入M，N，编程计算并输出这N个人原来在圈中的位置。    public static void reverseJosephusWinner(int M,int N){        LinkedList 
        
          linkedList=new LinkedList
         
          ();        for(int i=0;i
          
           N-1) index=0; else index++; } } public static void main(String args[]) { JosephusWinner3(5,9); reverseJosephusWinner(5,9); }}