国王和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);
	}
}

代码写的不好。

评论

45 楼 kukuwuwu 2010-01-14  

langshao 写道

kukuwuwu 写道

我觉得这应该是个逻辑题，结果应该是一个方案， 而不是多少天能出来
可以这样，
1. 指定100其中的一个人来做管理员
2. 管理员第一次出来放风时候把灯打开
3. 其他人放风的时候， 如果自己是第一次出来 看灯的状态，如果是亮的，那么关闭它
4. 其他人如果不是第一次出来，不改变灯的状态，关着就让它关着，开着就让它开着
5. 如果第一次出来的时候 灯为关闭状态， 那么不改变状态，并且当自己没出来，下次出来仍然是第一次出来
6. 当管理员再次出来时候如果灯是关闭的 说明除他之外有一个人放出来了 心中的计数器加1， 并把灯打开， 如果灯是开着的，说明除他之外没有人出来过， 不做任何操作

如果灯一开始就是关着的，管理员如何确定是否有人出来过？

算多少天只是好奇一般情况下他们还能不能活着出来

如果灯一开始关着的， 管理员就当一个人都没出来过， 其他人第一次出来时 灯是关着的  也当自己没出来过，见弟5条

44 楼 langshao 2010-01-14  

52356 写道

我要是国王，我就关一个囚犯100年都不放他一次风。
不知道贴代码的兄弟们，你们是怎么算出他们多少年后获得自由的？
别钻我空子，就按题中要求，随机让一个囚犯放风，可就有这么一个囚犯他点背啊，点背了200年也没被放过风，怎么办？这种小概率事件也是可能发生的。

题目说明是完全随机的，所以直接用了java.util.Random，算出来的可以作为期望值吧？

43 楼 langshao 2010-01-14  

kukuwuwu 写道

我觉得这应该是个逻辑题，结果应该是一个方案， 而不是多少天能出来
可以这样，
1. 指定100其中的一个人来做管理员
2. 管理员第一次出来放风时候把灯打开
3. 其他人放风的时候， 如果自己是第一次出来 看灯的状态，如果是亮的，那么关闭它
4. 其他人如果不是第一次出来，不改变灯的状态，关着就让它关着，开着就让它开着
5. 如果第一次出来的时候 灯为关闭状态， 那么不改变状态，并且当自己没出来，下次出来仍然是第一次出来
6. 当管理员再次出来时候如果灯是关闭的 说明除他之外有一个人放出来了 心中的计数器加1， 并把灯打开， 如果灯是开着的，说明除他之外没有人出来过， 不做任何操作

如果灯一开始就是关着的，管理员如何确定是否有人出来过？

算多少天只是好奇一般情况下他们还能不能活着出来

42 楼 52356 2010-01-14  

我要是国王，我就关一个囚犯100年都不放他一次风。
不知道贴代码的兄弟们，你们是怎么算出他们多少年后获得自由的？
别钻我空子，就按题中要求，随机让一个囚犯放风，可就有这么一个囚犯他点背啊，点背了200年也没被放过风，怎么办？这种小概率事件也是可能发生的。

41 楼 langshao 2010-01-14  

zhaolaiwei 写道

1、他们可以在15分钟时间内选一个计数员
2、计数员负责计数和开灯（灯开着就不用开了）
3、剩下的人每人出去的任务就是关灯（每个人只能关灯一次）
4、直到计数员计的人数为99人，则OK.

如果灯的初始状态是关的，而计数员幸运地第一个放风，那就杯具了。

40 楼 kukuwuwu 2010-01-14  

我觉得这应该是个逻辑题，结果应该是一个方案， 而不是多少天能出来
可以这样，
1. 指定100其中的一个人来做管理员
2. 管理员第一次出来放风时候把灯打开
3. 其他人放风的时候， 如果自己是第一次出来 看灯的状态，如果是亮的，那么关闭它
4. 其他人如果不是第一次出来，不改变灯的状态，关着就让它关着，开着就让它开着
5. 如果第一次出来的时候 灯为关闭状态， 那么不改变状态，并且当自己没出来，下次出来仍然是第一次出来
6. 当管理员再次出来时候如果灯是关闭的 说明除他之外有一个人放出来了 心中的计数器加1， 并把灯打开， 如果灯是开着的，说明除他之外没有人出来过， 不做任何操作

39 楼 52356 2010-01-14  

这个帖子越看越欢乐。
记得上大学的时候和寝室里的哥们一起看电视剧，里面演了“一个好人”和“一个坏人”，那个坏人在算计那个好人。
寝室里的哥们吼道：“你个傻x，你不知道那个人是坏人吗？”。
我吼道：“你个傻x，你知道谁是坏人，可他不知道”。

联系本题：
我们可以知道谁是第几天被放风，也知道他们放风时都干了什么，我们更可以知道他们每天吃了什么。但是，囚犯们之间是不知道的。

38 楼 langshao 2010-01-14  

realreal2000 写道

99个人每个人只能开灯两次，一个人负责关灯，当他关198次的时候，就可以一起解放了

import java.util.Random;

public class Prisoner2 {
	/**
	 * 犯人数目（大于1）
	 */
	private static final int PRISONER_COUNT = 100;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int minYear = Integer.MAX_VALUE;
		int maxYear = Integer.MIN_VALUE;
		for (int i = 0; i < 100; i++) {
			int year = prisonBreak();
			if (minYear > year) {
				minYear = year;
			}
			if (maxYear < year) {
				maxYear = year;
			}
			System.out.print(prisonBreak() + ",");
		}
		System.out.println();
		System.out.println("MinYear:" + minYear);
		System.out.println("MaxYear:" + maxYear);
	}

	private static int prisonBreak() {
		Random r = new Random();
		boolean lightOn = r.nextBoolean(); // 灯的初始状态
		int[] prisoner = new int[PRISONER_COUNT]; // 犯人，其值为开灯次数，最多两次
		final int COUNTER_ID = r.nextInt(PRISONER_COUNT); // 随机指定计数员，只负责关灯
		int counter = 0; // 计数员记下的关灯次数
		int days = 0; // 总共所花的天数
		int freeCount = (PRISONER_COUNT - 1) * 2; // 关灯次数达到此数时就自由了
		while (counter < freeCount) {
			days++;
			int n = r.nextInt(PRISONER_COUNT); // 随机出来放风的犯人
			if (n == COUNTER_ID) {// 计数员
				if (lightOn) { // 灯是开的就关灯
					lightOn = false;
					counter++;
					prisoner[COUNTER_ID]++; // 计数员记的是关灯数
				}
			} else { // 其他犯人
				if (!lightOn && prisoner[n] < 2) { // 灯是关的，且开灯次数不超过2
					lightOn = true;
					prisoner[n]++;
				}
			}
		}
		// 检查结果
		int sum = 0;
		for (int i = 0; i < PRISONER_COUNT; i++) {
			if (prisoner[i] > 0) { // 开过灯，则证明其放过风
				sum++;
			}
		}
		assert sum == PRISONER_COUNT : "something wrong.";
		return days / 365; // 大约
	}
}

某次运行结果：
56,51,59,53,57,52,49,58,58,59,59,53,56,54,54,58,57,57,57,48,61,57,51,54,52,59,53,58,53,54,56,59,58,60,60,57,52,55,55,53,62,58,52,58,52,53,50,55,55,56,59,51,57,53,55,49,53,59,55,54,55,54,64,57,53,59,52,51,52,52,57,55,54,56,64,51,51,56,49,49,55,52,53,59,52,55,58,52,52,56,63,60,53,50,46,49,55,52,53,55,
MinYear:46
MaxYear:68

自由来得迟了些，如果知道灯的初始状态会快些。
万一有人等不到自由就挂了，那就可能害死别人啦

37 楼 hite 2010-01-14  

mountainhunter 写道

得考虑路灯刚开始 是亮 还是灭吧
不然有问题

如果 有人确定自己是第一个的话，也没影响。

如果 无法确定，那可以把第一次获得的计数抛弃。

36 楼 52356 2010-01-14  

再次强调一下：
我认为“灯”的初始状态是这个问题中最不稳定的要素。灯的初始状态不确定，囚犯们商量的时候就有了麻烦。因为15分钟后，他们之间无法交流，也就是说，唯一给他们交流的工具就是“灯”。如果在他们被关押的期间，灯的状态是混乱的，那么他们必死无疑。所以，在他们仅有的15分钟讨论时间里，他们要统一一套规则。

楼上楼下的朋友们，给出方案的时候要保证你的方案是严密的。

35 楼 去你姑 2010-01-14  

看得够晕了，好难啊。
而且以上提到的不确定因素应该会影响结果吧，至少如果计数员不指定，好像就会乱了……

34 楼 zhaolaiwei 2010-01-14  

1、他们可以在15分钟时间内选一个计数员
2、计数员负责计数和开灯（灯开着就不用开了）
3、剩下的人每人出去的任务就是关灯（每个人只能关灯一次）
4、直到计数员计的人数为99人，则OK.

33 楼 52356 2010-01-14  

phoenix520 写道

52356 写道

这个问题我有几点看法：
1、囚犯不知道时间，也就是说他们不知道自己会是第几个人。根据条件，他们更不知道是第几天。
2、囚犯随机的放风。这里可能出现同一囚犯放风多次的情况。
3、那个路灯是他们唯一交流的工具。
4、现在最大的问题是不知道灯的初始状态。

我的办法：
1、指定计数囚犯。100囚犯中指定一个唯一的计数囚犯。
2、规则：
（1）所有囚犯除计数囚犯外，当他是第1次放风的时候，如果灯是关着的则设置灯为开，以后再放风，不干涉灯的状态。但第1次放风时，如果灯是开着的，则自己认为自己没放过风。
（2）计数囚犯统计灯开的次数，统计之后将灯关闭。计数到99时，结束。

细节解释：当计数囚犯第1次出门，如果灯是开着的。会有3种情况：1、灯默认是开着的，他是第1个放风的。2、灯是默认开着的，其他囚犯没有去碰开关。3、灯初始是关着的，一放风囚犯将它改为开。
现在问题出现了，由于不知道灯的初始状态，所以在计数囚犯计第1个数时是有误差的，误差为1人。但如果，计数囚犯放风时看到灯是关着的，那就万事大吉了。

这个思路蛮不错的，但是我还有个疑问：
计数员关灯99次的时候，就说明大家都出来过了，如果灯最初是开着的，那么第一个将灯关闭的人肯定是计数员，计数员认为已经有一个人出来过了(其实还没人出来过)，当出来到第98个的时候，计数员就已经数到99，认为大家都出来过了，然后大家都被拉出去砍头了。如果计数员考虑到这种情况，打算多数一个到100，当初始灯是关着的时候，他们就永远都出不去了，因为大家都只开一次，永远都到不了100.

你的这个疑问也是我的疑问。只是我在表述的时候没做过多的描述。这个问题不难想，但就是灯的初始状态让我抓狂。
所有囚犯都共有的属性：
1、不知道时间。当然也不知道谁是第1个被放风的。
2、他们能做的只有对灯的开关进行操作，同时知晓当前灯的状态。
3、每名囚犯被放风的次数不确定。（有点被的关到死也没被放过风，那就悲剧了。）

我的思路就是我之前说的那样，把握住1点：计数要精确。计数的囚犯要确定他每次计数，记录的是一个按要求操作路灯的囚犯。

这里强调一点，囚犯们都不知道灯的初始状态，题中也没说。所以，有人说囚犯进牢房前偷偷的看一眼灯的状态是不科学的。

32 楼 langshao 2010-01-14  

liyun_1981 写道

这个题蛮有意思的，发现前面有些同学都走进死胡同了，呵呵。
说下我的思路：
1、在100个囚犯中任意指定一个为计数员，他第一次放风时改变灯的状态，以后每次放风时如果发现灯的状态较上一次改变了，就改变灯的状态，并使计数值累加1，待到计数值累加到99时就可以确保每个囚犯都放风过了。
2、其它的99个囚犯都记住第一次放风时灯的状态，在以后的放风活动中，当第一次发现灯的状态较上一次改变了，就改变灯的状态，且此后的放风活动中再也不改变灯的状态。

假设顺序如下：
1. 犯人A放风，灯是开的，根据(2)，什么也不做，记下灯是开的
2. 计数员放风，灯是开的，根据(1)，记下灯是开的，灯变为关的
3. 犯人B放风，灯是关的，根据(2)，什么也不做，记下灯是关的
4. 犯人A放风，灯是关的，根据(2)，灯变为开的
5. 犯人B放风，灯是开的，根据(2)，灯变为关的
6. 计数员放风，灯是关的，根据(1)，计数+1，灯变为开的（？）

因为犯人A和B以后再也不改变灯的状态，是不是漏计了一个，而永远到不了100？

31 楼 liyun_1981 2010-01-14  

lolopig 写道

我的理解是记数员是不是第一个出去的没有关系，灯的初始状态也没有关系。
记数员自己第一次出去发现灯是关的，那么99次就可以了。
如果记数员第一次出去发现灯是开的，那么为了保证万无一失，多记数一次就可以了。

这位同学请你仔细体会下我上面说的思路，你的第一句话没错，可从你后面的说法来看，你还真没细想，呵呵。

30 楼 realreal2000 2010-01-14  

99个人每个人只能开灯两次，一个人负责关灯，当他关198次的时候，就可以一起解放了

29 楼 lolopig 2010-01-14  

我的理解是记数员是不是第一个出去的没有关系，灯的初始状态也没有关系。
记数员自己第一次出去发现灯是关的，那么99次就可以了。
如果记数员第一次出去发现灯是开的，那么为了保证万无一失，多记数一次就可以了。

28 楼 liyun_1981 2010-01-14  

这个题蛮有意思的，发现前面有些同学都走进死胡同了，呵呵。
说下我的思路：
1、在100个囚犯中任意指定一个为计数员，他第一次放风时改变灯的状态，以后每次放风时如果发现灯的状态较上一次改变了，就改变灯的状态，并使计数值累加1，待到计数值累加到99时就可以确保每个囚犯都放风过了。
2、其它的99个囚犯都记住第一次放风时灯的状态，在以后的放风活动中，当第一次发现灯的状态较上一次改变了，就改变灯的状态，且此后的放风活动中再也不改变灯的状态。

27 楼 phoenix520 2010-01-14  

52356 写道

这个问题我有几点看法：
1、囚犯不知道时间，也就是说他们不知道自己会是第几个人。根据条件，他们更不知道是第几天。
2、囚犯随机的放风。这里可能出现同一囚犯放风多次的情况。
3、那个路灯是他们唯一交流的工具。
4、现在最大的问题是不知道灯的初始状态。

我的办法：
1、指定计数囚犯。100囚犯中指定一个唯一的计数囚犯。
2、规则：
（1）所有囚犯除计数囚犯外，当他是第1次放风的时候，如果灯是关着的则设置灯为开，以后再放风，不干涉灯的状态。但第1次放风时，如果灯是开着的，则自己认为自己没放过风。
（2）计数囚犯统计灯开的次数，统计之后将灯关闭。计数到99时，结束。

细节解释：当计数囚犯第1次出门，如果灯是开着的。会有3种情况：1、灯默认是开着的，他是第1个放风的。2、灯是默认开着的，其他囚犯没有去碰开关。3、灯初始是关着的，一放风囚犯将它改为开。
现在问题出现了，由于不知道灯的初始状态，所以在计数囚犯计第1个数时是有误差的，误差为1人。但如果，计数囚犯放风时看到灯是关着的，那就万事大吉了。

这个思路蛮不错的，但是我还有个疑问：
计数员关灯99次的时候，就说明大家都出来过了，如果灯最初是开着的，那么第一个将灯关闭的人肯定是计数员，计数员认为已经有一个人出来过了(其实还没人出来过)，当出来到第98个的时候，计数员就已经数到99，认为大家都出来过了，然后大家都被拉出去砍头了。如果计数员考虑到这种情况，打算多数一个到100，当初始灯是关着的时候，他们就永远都出不去了，因为大家都只开一次，永远都到不了100.

26 楼 realreal2000 2010-01-14  

99个人只能开灯，只有一个人可以关灯