国王和100个囚犯

package com.azure.prisoner;

import java.util.ArrayList;

public class Algo3 {

	// 信号灯 囚徒只能开且开一次灯
	private boolean light;

	// 运行天数
	private int dayCount;

	// 囚徒个数
	private final int prisonerNum = 100;

	// 监狱
	private ArrayList<Prisoner> prisoners;

	private boolean debug;

	private String debugString;

	public static void main(String[] args) {
		int times = 100;
		double count = 0d;
		for (int i = 0; i < times; i++) {
			count += new Algo3().go();
			System.out.println("=============================");
		}
		System.out.println("运行" + times + "次，平均每次花费" + count / times / 365
				+ "年");
	}

	private int go() {

		light = true;
		dayCount = 0;

		// 初始化100个囚徒
		prisoners = new ArrayList<Prisoner>();
		for (int i = 0; i < 100; i++) {
			prisoners.add(new Prisoner(i));
		}
		// 初始化计数者数组
		Counter[] counters = new Counter[2];

		boolean find = false;
		// 循环，直到找到100个出去放过风的囚徒
		while (!find) {
			dayCount++;
			// System.out.print(dayCount + ":");

			// 随机抽取一个囚徒放风
			int random = (int) (Math.random() * (prisonerNum));
			Prisoner outedPrisoner = prisoners.get(random);

			// 取得时间片段
			int timePeriod = getTimePeriod();

			switch (timePeriod) {
			case 1:
				// 初始化交流片段
				System.out.println("==初始化交流片段==");
				counters[0].setCout(false);
				counters[1].setCout(false);

				if (light) {
					if (outedPrisoner instanceof Counter) {
						Counter c = (Counter) outedPrisoner;
						c.count++;
						c.debugString = c.debugString + "," + debugString;
						System.out.println(c.id + "找到 " + debugString + ",总计"
								+ c.count + "开灯");
					} else {
						System.out.println(dayCount + ":" + debugString + "被加到"
								+ outedPrisoner.id + "的cache中");
						outedPrisoner.cache++;
					}
					light = false;
				}
				break;
			case 2:
				// 结束交流片段
				System.out.println("==结束交流片段==");
				if (light) {
					System.out
							.println(dayCount + ":" + outedPrisoner.id + "关灯");
					light = false;
				}
				break;
			case 3:
				// 交流片段
				// System.out.println("交流片段");
				if (outedPrisoner instanceof Counter) {
					Counter c = (Counter) outedPrisoner;

					if (c.Cout) {
						break;
					}

					if (!light && c.count == 50) {
						light = true;
						System.out.println(dayCount + ":" + outedPrisoner.id
								+ "关灯");
						c.setCout(true);

					} else if (light && c.count == 50) {
						find = true;
						System.out.println("\nSUCCEED!");
					}
				}
				break;
			case 4:
			default:
				// 计数片段
				// System.out.println("计数片段");
				if (counters[0] == null) {
					Counter counter = new Counter(outedPrisoner.id);
					light = false;
					System.out
							.println(dayCount + ":" + outedPrisoner.id + "开灯");
					counter.count++;
					prisoners.set(outedPrisoner.id, counter);
					counters[0] = counter;
					break;
				}

				if (counters[1] == null) {
					if (!outedPrisoner.equals(counters[0])) {
						Counter counter = new Counter(outedPrisoner.id);
						light = false;
						System.out.println(dayCount + ":" + outedPrisoner.id
								+ "开灯");
						counter.count++;
						prisoners.set(outedPrisoner.id, counter);
						counters[1] = counter;
					}
					break;
				}

				if (outedPrisoner instanceof Counter) {
					Counter c = (Counter) outedPrisoner;
					if (light && c.count < 50) {
						c.count++;
						light = false;
						System.out.println(c.id + "找到 " + debugString + ",总计"
								+ c.count + "开灯");
						c.debugString = c.debugString + "," + debugString;
						debugString = "";
					} else if (!light && c.count > 50) {
						c.count--;
						light = true;
					}
					break;
				}

				// System.out.println("囚徒在放风");
				if (!light) {
					if (outedPrisoner.cache > 0) {
						debugString = "cache_" + outedPrisoner.id;
						outedPrisoner.cache--;
						System.out.println(dayCount + ":" + outedPrisoner.id
								+ "cache--关灯");
						light = true;
					} else if (!outedPrisoner.isOut()) {
						outedPrisoner.setOut(true);
						light = true;
						System.out.println(dayCount + ":" + outedPrisoner.id
								+ "囚徒关灯");
						debugString = outedPrisoner.id + "";
					}
				}
				break;
			}

			if (dayCount == 60000) {
				System.out.println();
				for (Prisoner p : prisoners) {
					System.out.println((p instanceof Counter) ? "counter"
							+ p.id + ":" + ((Counter) p).debugString : p.id
							+ ":" + p.isOut() + ":" + p.cache);
				}
				System.out.println(counters[0].count + ":" + counters[1].count);
				debug = true;
				System.exit(0);
			}
		}
		return dayCount;
	}

	public int getTimePeriod() {
		int period = 1000;
		int cPeriod = 200;

		if (dayCount % period == 0) {
			return 2;
		} else if (dayCount % period == (period - cPeriod)) {
			return 1;
		} else if (dayCount % period > ((period - cPeriod))
				&& dayCount % period < period) {
			return 3;
		} else {
			return 4;
		}
	}

	/**
	 * 囚徒类
	 * 
	 * @author Justis_ren
	 * 
	 */
	class Prisoner {

		public int id;

		// 是否有过有效放风
		private boolean out;

		public int cache;

		public Prisoner(int id) {
			this.id = id;
		}

		public boolean isOut() {
			return out;
		}

		public void setOut(boolean out) {
			this.out = out;
		}
	}

	class Counter extends Prisoner {
		private int count;
		private boolean Cout;
		public String debugString;

		public Counter(int id) {
			super(id);
		}

		public boolean isCout() {
			return Cout;
		}

		public void setCout(boolean cout) {
			Cout = cout;
		}
	}
}