一百个猴子围城一个圈，随机选一个猴子，标号为1，顺时针然后给每个猴子编下号一直到100只猴子。然后1，2，1，2 的报数，报2的猴子就退出，求最后剩上来的猴子的编号

一百个猴子围城一个圈，随机选一个猴子，标号为1，顺时针然后给每个猴子编上号一直到100只猴子。然后1，2，1，2 的报数，报2的猴子就退出，求最后剩下来的猴子的编号

package com.mmq;

/**
 * 一百个猴子围城一个圈，随机选一个猴子，标号为1，
 * 顺时针然后给每个猴子编上号一直到100只猴子。然后1，2，1，2 的报数，
 * 报2的猴子就退出，求最后剩下来的猴子的编号
 * 
 * @use
 * @ProjectName stuff
 * @Author <a href="mailto:mhmyqn@qq.com">mikan</a></br>
 * @Date 2013-2-27 下午01:03:23 </br>
 * @FullName com.mmq.MonkeyTest.java </br>
 * @JDK 1.6.0 </br>
 * @Version 1.0 </br>
 */
public class MonkeyTest {

	public static void main(String[] args) {
		MonkeyTest mt = new MonkeyTest();
		Monkey[] list = mt.initialize(100);
		Monkey mc = mt.findMonkey(list[0]);
		System.out.println("monkey number is :" + mc.getValue());
	}
	
	/**
	 * 初始化
	 * @param size
	 * @return
	 */
	public Monkey[] initialize(int size) {
		Monkey[] mcs = new Monkey[size];
		Monkey previous = null;
		for (int i = 1; i <= size; i++) {
			if (i > 1) {
				previous = mcs[i-2];
			}
			Monkey mc = new Monkey();
			if (i <= size && i > 1) {
				previous.setNext(mc);
			} else if (i == size) {
				mc.setNext(mcs[0]);
			}
			mc.setValue(i);
			mc.setPrevious(previous);
			mcs[i-1] = mc;
		}
		mcs[0].setPrevious(mcs[size - 1]);
		mcs[size - 1].setNext(mcs[0]);
		return mcs;
	}
	
	/**
	 * 查找最后剩下的猴子
	 * @param mc
	 * @return
	 */
	public Monkey findMonkey(Monkey mc) {
		Monkey current = mc;
		Monkey next = mc.getNext();
		int count = 1;
		// 当前节点前一个节点的值和当前节点下一个节点的值相等时表示最后一个
		while (current.getPrevious().getValue() != current.getNext().getValue()) {
			if (count % 2 == 0) {
				current.getPrevious().setNext(current.getNext());
				current.getNext().setPrevious(current.getPrevious());
			}
			current = next;
			next = current.getNext();
			count++;
		}
		return current;
	}
}

class Monkey {
	
	private Monkey previous;
	
	private Monkey next;
	/**
	 * 当前值
	 */
	private Integer value;

	public Monkey getPrevious() {
		return previous;
	}

	public void setPrevious(Monkey previous) {
		this.previous = previous;
	}

	public Monkey getNext() {
		return next;
	}

	public void setNext(Monkey next) {
		this.next = next;
	}

	public Integer getValue() {
		return value;
	}

	public void setValue(Integer value) {
		this.value = value;
	}

	@Override
	public String toString() {
		return "value = " + value + ";previous = " + 
			(previous == null ? "" : previous.getValue()) + 
			";next = " + (next == null ? "" : next.getValue());
	}
}