| 粱远声:囚徒问题一个较好的解 |
| 送交者: 粱远声 2009年12月17日16:49:28 于 [五 味 斋] 发送悄悄话 |
|
有100个无期徒刑囚徒,被关在100个独立的小房间,互相无法通信。每天会有一个囚徒被随机地抽出来放风,随机就是说可能被抽到多次。放风的地方有一盏灯,囚徒可以打开或者关上,除囚徒外,没有别人会去动这个灯。每个人除非出来防风,是看不到这个灯的。
一天,全体囚徒大会,国王大赦,给大家一个机会:如果某一天,某个囚徒能够明确表示,所有的囚徒都已经被放过风了,而且的确如此,那么所有囚徒释放;如果仍有囚徒未被放过风,那么所有的囚徒一起处死! 囚徒大会后给大家20分钟时间讨论, 如果你是其中的一员,应怎样利用这20分钟的时间来制定一个切实可行的办法呢? 如果说是某一个囚犯一直无法抽到出去放风,那他们就确实无法出去了。不需要考虑这样的可能哦。 这题确实比较难。补充一下:不要去考虑什么犯人突然死亡的意外因素。是纯粹的理论题。 一个较好的解 囚徒经过20分钟时间讨论,产生如下解答。 假设灯的初始状态是开着(亮)的。 定义一个组长:组长是1到100天里第一个两次放风的人。 定义先驱者:先驱者是1到100天里第一次放风且看到灯是开着的人。先驱者什么都不做,只记住自己是先驱者。 组长在第二次放风的时候,把灯关上。如果是第n+1天来的,记住放风人数 n 1到99天里放风且看到灯是关(熄)着的人什么也不做。 定义一个付组长:第100天放风的人。如果灯是开着的且是第一次放风,立刻宣布所有人都放过风了。 如果灯是关着的,什么都不做。 从101天开始,先驱者放风,什么都不做。非先驱者,非组长放风:如果灯是关着的且从未开过灯的人把灯打开(亮),否则什么都不做。 组长放风的时,如果灯是开着(亮)的,把灯关上,计数一次。如果灯是关着的,什么都不做。 如果组长计数 k = 100-n 次时,宣布所有人都放过风了。 |
|
![]() |
![]() |
| 实用资讯 | |
|
|
| 一周点击热帖 | 更多>> |
| 一周回复热帖 |
| 历史上的今天:回复热帖 |
| 2008: | 很想知道,有时看到有人说老棒子,一般 | |
| 2008: | 老全疯了,我不跟丫计较。反正丫也没几 | |
| 2007: | 小城圣诞游行——和铁狮子圣诞系列 | |
| 2007: | 天下通吃 – 吞掉半只牛 | |
| 2006: | 闲谈一句俗话----老婆是别人的好 | |
| 2006: | 老娘舅的山海经:姐妹道 | |
| 2005: | 娶个四川女孩子做老婆 | |
| 2005: | 闲谈PK | |
| 2004: | 上官天乙: 对网友的回复 | |
| 2004: | 狗蛋儿的故事 | |




