国王和100个囚犯 -

lolopig

浏览: 7421 次
性别:
来自: 厦门

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

国王和100个囚犯

游戏能源面试多线程 J#

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

代码写的不好。

分享到：

js浮点数的加减乘除运算函数

2010-01-13 14:53
浏览 4323
评论(105)
论坛回复 / 浏览 (105 / 36076)
分类:编程语言
查看更多

65 楼 AntFlow 2010-01-14

hkliya 写道

什么也看不到，听不到，连时间都感觉不到，吃饭也没点儿。。。唯一的娱乐就是不定期的去院子里玩那不知道被多少人玩过的破灯。。。
要是我是犯人，不是prison break就是咬舌自尽，一了百了，谁跟这无聊又变态的国王烂人玩这破游戏。。。

照这个游戏规则玩，估计出去的时候国王都已经死了，找谁说理去。。。

你要是咬舌自尽了，那个计数员数到98的时候就杯具了。。。99永远不会来了

64 楼 lolopig 2010-01-14

kukuwuwu 写道

langshao 写道

中国大人写道

langshao 写道

中国大人写道

langshao 写道

中国大人写道

kukuwuwu 写道

langshao 写道

kukuwuwu 写道

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

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

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

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

kukuwuwu正解,没看出漏洞来.

我实在看不明！
3-5是不是说“第一次看到灯开就关”？
第2条，如果管理员第一次出来看到灯是开着的，怎办？
其他人都在管理员第一次出来之后才出来？

管理员第一次出来开到灯是开着的,不管,让它开着.直到有一次看到灯是关闭的为止.计数,打开灯.等待下一次的关闭.

就是其他犯人看到灯是开的，关了？
那么，如果刚开始灯就是开的，其他犯人关，还是不关？他们能知道管理员出来过吗？

刚开始的时候灯开的,犯人关掉.不论什么情况下,只要管理员确定是他自己开的灯,以后的某一次看到灯关掉了,他就可以记一次数.

哦，这样管理员确实知道从什么时候开始计数。按你的说法，管理员不记之前的人数。那么，关灯那位兄弟，他怎么知道下次还要不要关灯呢？管理员可还没有算上他啊！

哎呀，对哈，遗漏了，继续想ing....

确实灯的初始状态非常重要，之前考虑的时候没有想清楚，以为可以忽略第一次，仔细想下，有种情况如果忽略了第一次那么就永远都达不到99次了。。

63 楼 langshao 2010-01-14

hkliya 写道

如果是10个犯人呢？一般在一年内就能出去了（概率大于99%）！

62 楼 hkliya 2010-01-14

61 楼 kukuwuwu 2010-01-14

langshao 写道

中国大人写道

langshao 写道

中国大人写道

langshao 写道

中国大人写道

kukuwuwu 写道

langshao 写道

kukuwuwu 写道

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

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

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

kukuwuwu正解,没看出漏洞来.

管理员第一次出来开到灯是开着的,不管,让它开着.直到有一次看到灯是关闭的为止.计数,打开灯.等待下一次的关闭.

就是其他犯人看到灯是开的，关了？
那么，如果刚开始灯就是开的，其他犯人关，还是不关？他们能知道管理员出来过吗？

刚开始的时候灯开的,犯人关掉.不论什么情况下,只要管理员确定是他自己开的灯,以后的某一次看到灯关掉了,他就可以记一次数.

哎呀，对哈，遗漏了，继续想ing....

60 楼 xbcoil 2010-01-14

好神奇啊...看了不错..

59 楼 metaphy 2010-01-14

52356 写道

langshao 写道

52356 写道

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

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

这个问题如果要计算他们多少天后能自由的话，我们也只能算出个最短天数。最初看到这个问题时，我的第1反应就是这里有许多不确定的要素。
我认为，这个问题可以用“代码”描述。但是要用代码计算出个精确结果是不可取的。

这个题目当然没有精确解，白痴都知道

58 楼 mountainhunter 2010-01-14

langshao 写道

javaeye_hua 写道

zhaolaiwei 写道

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

观点相同。
就初始灯状态说明下操作：
A为计数员，Bn为剩余99人。
A只能开灯。
Bn只能关灯，且每人只能关一次。
从开始计数，A看到99次关着的灯后就能确定100人都出来放过风。
A第一次出来时：
见到灯是关着的，就打开，然后开始计数：以后每次出来，见到灯关了，就打开，计数一次。
灯若开着，不操作灯，开始计数。
A每次出来，见到灯关着就计数累加一次。

Bn出来放风，见到灯亮着，且自己没有关过灯，就关掉灯。【确保没人只关一次灯】

这样，等到A计数到99后，就能证明100人都出去过了。

灯亮着，Bn出来，关灯，A还没出来过，以后这位关过灯的Bn再也不关灯了，A就漏了这位Bn啦

然后就"死锁"啦 A永远看不到第99次计数了

57 楼 mountainhunter 2010-01-14

hite 写道

mountainhunter 写道

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

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

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

如果有人能确定自己是第一个的话确实没什么问题
如果无法确定，不能简单的把第一次的记数抛弃，因为你抛弃了，而这次计数又是有效的话，那么到最后，计数员就永远在那里等待最后一次计数，而其余的人也不会再去关灯，因为他们都已经关了一次了，就都老死了...

56 楼 langshao 2010-01-14

javaeye_hua 写道

zhaolaiwei 写道

灯亮着，Bn出来，关灯，A还没出来过，以后这位关过灯的Bn再也不关灯了，A就漏了这位Bn啦

55 楼 langshao 2010-01-14

langshao 写道

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; // 大约
	}
}

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

 assert sum == PRISONER_COUNT : "something wrong.";

不起作用，原来要加-ea，即 java -ea Prisoner2 。

54 楼 javaeye_hua 2010-01-14

zhaolaiwei 写道

53 楼 langshao 2010-01-14

中国大人写道

langshao 写道

中国大人写道

langshao 写道

中国大人写道

kukuwuwu 写道

langshao 写道

kukuwuwu 写道

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

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

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

kukuwuwu正解,没看出漏洞来.

管理员第一次出来开到灯是开着的,不管,让它开着.直到有一次看到灯是关闭的为止.计数,打开灯.等待下一次的关闭.

就是其他犯人看到灯是开的，关了？
那么，如果刚开始灯就是开的，其他犯人关，还是不关？他们能知道管理员出来过吗？

刚开始的时候灯开的,犯人关掉.不论什么情况下,只要管理员确定是他自己开的灯,以后的某一次看到灯关掉了,他就可以记一次数.

52 楼中国大人 2010-01-14

langshao 写道

中国大人写道

langshao 写道

中国大人写道

kukuwuwu 写道

langshao 写道

kukuwuwu 写道

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

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

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

kukuwuwu正解,没看出漏洞来.

管理员第一次出来开到灯是开着的,不管,让它开着.直到有一次看到灯是关闭的为止.计数,打开灯.等待下一次的关闭.

就是其他犯人看到灯是开的，关了？
那么，如果刚开始灯就是开的，其他犯人关，还是不关？他们能知道管理员出来过吗？

刚开始的时候灯开的,犯人关掉.不论什么情况下,只要管理员确定是他自己开的灯,以后的某一次看到灯关掉了,他就可以记一次数.

51 楼 langshao 2010-01-14

中国大人写道

langshao 写道

中国大人写道

kukuwuwu 写道

langshao 写道

kukuwuwu 写道

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

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

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

kukuwuwu正解,没看出漏洞来.

管理员第一次出来开到灯是开着的,不管,让它开着.直到有一次看到灯是关闭的为止.计数,打开灯.等待下一次的关闭.

就是其他犯人看到灯是开的，关了？
那么，如果刚开始灯就是开的，其他犯人关，还是不关？他们能知道管理员出来过吗？

50 楼中国大人 2010-01-14

langshao 写道

中国大人写道

kukuwuwu 写道

langshao 写道

kukuwuwu 写道

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

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

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

kukuwuwu正解,没看出漏洞来.

管理员第一次出来开到灯是开着的,不管,让它开着.直到有一次看到灯是关闭的为止.计数,打开灯.等待下一次的关闭.

49 楼 langshao 2010-01-14

中国大人写道

kukuwuwu 写道

langshao 写道

kukuwuwu 写道

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

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

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

kukuwuwu正解,没看出漏洞来.

48 楼 52356 2010-01-14

langshao 写道

52356 写道

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

47 楼中国大人 2010-01-14

kukuwuwu 写道

langshao 写道

kukuwuwu 写道

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

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

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

kukuwuwu正解,没看出漏洞来.

46 楼 kukuwuwu 2010-01-14

langshao 写道

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

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

如果那个管理员一直随机不到他，他们得关一辈子哈哈

« 上一页 1 2 3 4 5 6 下一页 »

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

国王和100个囚犯

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

国王和100个囚犯

评论

发表评论

相关推荐

最近访客更多访客>>