分别使用队列和双向链表解决约瑟夫环问题
昨天看到一个约瑟夫环的问题，写出来交流一下，欢迎大家来留下批评和建议。
/**
* 解决约瑟夫环圆圈问题 <br/>
* M个人围成一圈，从1数到N循环数数，数到N的退出圆圈，问最后留下的是谁？ <br/>
* @version 2011-08-21 1.0.0.0
*/
import java.util.LinkedList;import java.util.Queue;public class QuesCircle { //1、使用队列解答（经测试时间效率较高）public static int answerQueue(int M, int N){Queue<Integer> que = new LinkedList<Integer>();for(int i=1; i<=M; i++)que.offer(i);//没有报到N的人重新排到最后，报到N的出队列for(int i=1; que.size()>1; i++){if(i%N != 0)que.offer(que.poll());elseque.poll();}return que.poll();}//2、使用双向链表解答（经测试时间效率较低）public static int answerDoubleList(int M, int N){int temp;LinkedList<Integer> dou = new LinkedList<Integer>();for(int i=1; i<=M; i++)dou.add(i);temp = 0;/* * 移除报到N的人，将移除的位置+N-1对链表的大小取 * 模继续循环移除直至剩下最后一个。 */while(dou.size() > 1){temp = (temp + N - 1) % dou.size();dou.remove(temp);}return dou.poll();}}