国王和100个囚犯问题

原帖可见：http://www.iteye.com/topic/570744，问题大致如下：

 

国王招来100个囚犯，对他们说：你们犯的是死罪，本应该将你们统统杀掉，但我慈悲为怀，给你们一次求生的机会。15分钟以后，你们将被关进一个有100间隔离牢房的监狱里，每人一间牢房，都与外界隔绝，什么也听不见、看不到，连时间都没法计算，更别说获得外界的任何信息。（送饭除外，但也是不规律的送） 

这所监狱有一个院子，每天会随机（注意是完全随机）打开一间牢房的门，让那个囚犯到院子里来放风。院子里有一盏路灯，放风的囚犯可以控制它的开关，将它打开或是关闭。除囚犯之外，其他人都不会去碰开关。这盏灯会永远有充足的能源供应，如果灯泡坏了或是电路出了故障会马上修好，当然修理人员不会改变灯的状态（开或关）。 

除了开关这盏灯，放风的囚犯放风时留下的任何其它痕迹都会在夜晚被清除干净（包括在灯上作的任何记号）。 

牢房是完全封闭的，院子里的灯光在牢房里看不到。只有放风出到院子里的人才能看到。 

好了现在我向你们提出一个要求，只要你们做到了，就可以全部获得释放： 若干天以后，你们中只要有任何一个人能够向我证明所有的人都曾到院子里去过，你们就全体释放。当然要有证据！因为我只会给你们一次机会，如果向我证明的那个人无法自圆其说，你们就全部砍头。所以，要珍惜这次机会。如果你们永远做不到我的要求，你们就全部关到死。 

现在给你们15分钟商量你们的方案。15分钟以后，你们将被关进我刚才说的那个监狱，永远无法再交流。

这是我的解决方案：

package org.sunkui.demo;

import java.util.Random;

public class PrisonExample {
	Random rand = new Random();

	public static void main(String[] args) {
		PrisonExample p = new PrisonExample();
		p.method_1(true);
	}

	void method_1(boolean light) {
		int[] prisoner = new int[100];
		// counter prisoner, the first out
		int counter = rand.nextInt(100);
		// Light turn on or off from now on
		int counterLightOnOrOff = 1;
		// whether on or off the first time, and the counter turn on/off the
		// light right now
		boolean lightOnOrOff = !light;
		// starts right now
		int days = 0;
		// the first prisoner out
		prisoner[counter] = 1;

		while (true) {
			// include the counter
			int others = rand.nextInt(100);
			days++;

			if (others == counter && !lightOnOrOff) {
				// if light is in state initialize state, put it to opposite
				// state
				lightOnOrOff = !lightOnOrOff;
				counterLightOnOrOff++;
			} else {
				// other prisoners turn the light on or off just once
				if (prisoner[others] == 0 && lightOnOrOff) {
					lightOnOrOff = !lightOnOrOff;
					prisoner[others] = 1;
				}
			}

			if (counterLightOnOrOff == 100)
				break;
		}

		System.out.println("Total days: " + days);
	}
}