Josephus环

package com.apache.owen.link.josephus;

import java.util.ArrayList;
import java.util.List;

import junit.framework.TestCase;

/**
 * Josephus环
 * 已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
 * 
 * @author chenchen
 */
public class Josephus extends TestCase {
	public void test() {
		findMonkey(50000, 3);
		myJosephus(50000, 3, 1);
	}

	/**
	 * 使用纯数学方法来解决问题, 原算法未提供参数start
	 * length=30000000时, 运算时间才会超过1s
	 * length=200000时, 运算时间才会超过1ms
	 * step值对运算时间影响不大
	 * O(1)
	 * http://blog.csdn.net/MapReduce/archive/2007/04/02/1549494.aspx
	 * http://hi.baidu.com/wuxyy/blog/item/464471f03802fcafa40f523c.html
	 * http://hi.baidu.com/sulipol/blog/item/fb18458e5e6346e4f11f366e.html
	 * @param length   初始化队列的长度
	 * @param step     m
	 * @param start    k
	 * @return
	 */
	protected void findMonkey(int length, int step) {
		int start = 0;
		
		long startTime = System.currentTimeMillis();
		for (int i = 2; i <= length; i++){
			start = (start + step) % i;
		}
		long stopTime = System.currentTimeMillis();
		
		System.out.println("Josephus spend time: " + (stopTime - startTime) + "ms");
		System.out.println(start + 1);
	}

	/**
	 * 自己完成的方法: java通过模拟实际情况达到解决问题的目的
	 * step越小, 花的时间越长
	 * length=40000时, 运算时间会超过1s
	 * length=5000时, 运算时间会超过1ms
	 * O(nm)
	 * @param length
	 * @param step
	 * @param start
	 */
	protected void myJosephus(int length, int step, int start) {
		// 存储人员的队列
		List<String> list = new ArrayList<String>();
		for (int i = 1; i <= length; i++) {
			list.add(((Integer) i).toString());
		}
		// 开始报数的人所在队列中的排数, 初始化current=start-1, current为下标
		int current = start - 1;
		
		long startTime = System.currentTimeMillis();
		do {
			// 从自己开始数数, 所以-1
			current += step - 1;
			// 当current超过整个队列的实际长度时, 需要回到头继续数
			while (current >= list.size()) {
				current -= list.size();
			}
			// 数到m的那个人出列
			list.remove(current);
			// 继续数数, 直到留下最后的那个人
		} while (list != null && list.size() > 1);
		long stopTime = System.currentTimeMillis();
		
		System.out.println("Josephus spend time: " + (stopTime - startTime) + "ms");
		System.out.println(list.iterator().next());
	}
}