粱远声:囚徒问题一个较好的解 |
送交者: 粱远声 2009年12月17日18:05:36 于 [茗香茶语] 发送悄悄话 |
有100个无期徒刑囚徒,被关在100个独立的小房间,互相无法通信。每天会有一个囚徒被随机地抽出
来放风,随机就是说可能被抽到多次。放风的地方有一盏灯,囚徒可以打开或者关上,除囚徒外,没 有别人会去动这个灯。每个人除非出来防风,是看不到这个灯的。 一天,全体囚徒大会,国王大赦,给大家一个机会:如果某一天,某个囚徒能够明确表示,所有的囚 徒都已经被放过风了,而且的确如此,那么所有囚徒释放;如果仍有囚徒未被放过风,那么所有的囚 徒一起处死! 囚徒大会后给大家20分钟时间讨论, 如果你是其中的一员,应怎样利用这20分钟的时间来制定一个 切实可行的办法呢? 如果说是某一个囚犯一直无法抽到出去放风,那他们就确实无法出去了。不需要考虑这样的可能哦。 这题确实比较难。补充一下:不要去考虑什么犯人突然死亡的意外因素。是纯粹的理论题。 一个较好的解 囚徒经过20分钟时间讨论,产生如下解答。 定义一个组长:组长是1到100天里第一个两次放风的人。 定义先驱者:第一个放风的人,把灯打开。其它先驱者是第2到100天里第一次放风且看到灯是开着的 人。其它先驱者什么都不做。 组长在第二次放风的时候,把灯关上。如果是第n+1天来的,记住放风人数 n。 2到99天里放风且看到灯是关(熄)着的人什么也不做。 定义一个付组长:第100天放风的人。如果灯是开着的且是第一次放风,立刻宣布所有人都放过风了。 如果灯是关着的,什么都不做。 从101天开始,先驱者放风,什么都不做。非先驱者,非组长放风:如果灯是关着的且从未开过灯的 人把灯打开(亮),否则什么都不做。 组长放风的时,如果灯是开着(亮)的,把灯关上,计数一次。如果灯是关着的,什么都不做。 如果组长计数 k = 100-n 次时,宣布所有人都放过风了。 |
|
|
|
实用资讯 | |
|
|
一周点击热帖 | 更多>> |
|
|
一周回复热帖 |
|
|
历史上的今天:回复热帖 |
2008: | 青年时代的奥先知,帅照一张祝茶童鞋圣 | |
2008: | ZT: BBC中国听众:我现在非常拥护共产 | |
2007: | 加拿大,你们的技术移民怎么啦? | |
2007: | 体验深圳(2)-劳动密集型产业 | |
2006: | 木头谈酒(2)-喝啤酒 | |
2006: | 6-4,波士顿城外槐花香(职业本人图) | |
2005: | 莲花落(续四) | |
2005: | 已经没人会说满话了.... | |
2004: | 对杨振宁祖孙配现象的思考 | |
2004: | 对点小二及其他网友的回复 | |