国王和100个囚犯

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

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

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

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

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

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

public interface Demo {
	
	public void doBool(); 

}

public class Demo2 implements Demo{
	
	/**
	 * 普通囚犯
	 * 第一次见灯开着时关掉
	 * 无论出去多少回，只能关灯一次
	 */
	
	public int count = 0;
	public boolean first = true;
	public String name;
	
	@Override
	public void doBool() {
		// TODO Auto-generated method stub
		if(Test.bool && first){
			Test.bool = false;
			first = false;
		}
		count++;
	}
}

public class Demo3 implements Demo{
	
	/**
	 * 计数员
	 * 出去后就开灯
	 * 如果开着就不去动他
	 * 
	 * 直到第99次出去关灯的时候就是100个人都出去过了
	 */
	
	public int closeCount = 0;
	public String name;
	
	@Override
	public void doBool() {
		// TODO Auto-generated method stub
		if(!Test.bool){
			Test.bool = true;
			closeCount++;
			if(closeCount == 99){
				Test.ok = true;
			}
		}
	}
}

public class Test {

	public static boolean bool = false;
	public static boolean ok = false;

	public static void main(String[] args) {
		int num = 0;
		int count = 0;
		Demo[] demo = new Demo[100];
		Demo2 demo2;
		for (int i = 1; i <= 99; i++) {
			demo2 = new Demo2();
			demo2.name = "d" + i;
			demo[i - 1] = demo2;
		}
		Demo3 demo3 = new Demo3();
		demo3.name = "d100";
		demo[99] = demo3;

		while (true) {
			num = (int) (Math.random() * 100);
			demo[num].doBool();
			count++;
			if (ok)
				break;
		}

		for (int j = 0; j < demo.length - 1; j++) {
			Demo2 d2 = (Demo2) demo[j];
			System.out.println(d2.name + ":" + d2.count);
		}
		System.out.println("执行次数:" + count);
	}
}

代码写的不好。

评论

5 楼 metaphy 2010-01-13  

结果差不多。

package test.prisoner;

import java.util.Random;

public class Prisoner {
	public static void main(String[] args) {
		Random r = new Random();
		int[] prisoner = new int[100];
		final int COUNTER_ID = 0; // 任意指定计数员
		boolean lightOn = false;
		int counterLightOff = 0;
		int days = 0;

		while (true) {
			int n = r.nextInt(100);
			days++;
			if (n == COUNTER_ID) {
				if (!lightOn) {
					lightOn = true;
					counterLightOff++;
					prisoner[COUNTER_ID] = 1;
				}
			} else {
				if (lightOn) {
					if (prisoner[n] == 0) {
						lightOn = false;
						prisoner[n] = 1;
					}
				}
			}
			if (counterLightOff == prisoner.length)
				break;
		}

		// Result check
		int sum = 0;
		for (int i = 0; i < prisoner.length; i++) {
			sum += prisoner[i];
		}
		System.out.println(sum + " prisoners were out at least once!");
		System.out.println("Total days: " + days + "; years: " + days / 365);
	}
}

4 楼 metaphy 2010-01-13  

上面那个代码有点问题，就是假设每人都知道自己是不是第一个出来的。待会回去再写一个

3 楼 metaphy 2010-01-13  

嗯。有趣。 比较好奇他们得花多少年出来 －

import java.util.Random;

public class Prisoner {
	public static void main(String[] args) {
		Random r = new Random();
		int[] prisoner = new int[100];

		int n = r.nextInt(100);
		int counterID = n; // 第一天出去的那个就是记数员
		prisoner[n] = 1;
		int counterLightOff = 1;
		boolean lightOn = true;

		int days = 0;

		while (true) {
			n = r.nextInt(100);
			days++;

			if (n == counterID) {
				if (!lightOn) {
					lightOn = true;
					counterLightOff++;
				}
			} else {
				if (lightOn) {
					if (prisoner[n] == 0) {
						lightOn = false;
						prisoner[n] = 1;
					}
				}
			}
			if (counterLightOff == 100)
				break;
		}

		// Result check 
		int sum = 0;
		for (int i = 0; i < prisoner.length; i++) {
			sum += prisoner[i];
		}
		System.out.println(sum + " prisoners were out at least once!");
		System.out.println("Total days: " + days + "; years: " + days / 365);
	}
}

结果要25－35年

2 楼 clyman 2010-01-13  

能用foreach就foreach吧

1 楼 yangyi 2010-01-13  

只有这个办法，代码应该还可以再优化一下