[转帖]100囚徒难题

sunchuren · 发表于 2004-4-26 06:05:34

<

>有100个无期叫囚徒，被关在100个独立的小房间，互相无法通信。
每天会有一个囚徒被随机地抽出来放风，随机就是说可能被抽到多次。
放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每
个人除非出来防风，是看不到这个灯的。
一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表
示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒未
被放过风，那么所有的囚徒一起处死！
囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？

这个问题是著名的谜题之一，如果大家认为自己找到了方法，再仔细想想，有没有效率
更高的？

aquila_free · 发表于 2004-4-26 19:04:24

难，想

fredcash · 发表于 2004-4-29 00:39:11

的确很难，正在想。

roc_the_red · 发表于 2004-5-1 08:08:13

<

>好像有个很慢很慢很慢的办法，设定一个观察者，每次放风时如果看到灯亮，则把灯关上，灯灭，则不去管它。其他犯人放风时如果第一次看到灯灭，则把灯打开，但只做一次，以后不管看到什么情况都不再管它。这样，当观察者关过99次灯时，说明所有犯人都已放过风了。不知道这样行不行

liyunfei84 · 发表于 2004-5-9 02:38:43

这个办法还不错,总之,每个人防风时,是第一次就开灯,以后不管怎样见到等就让它灭,也就是说大家约定的那个人的前一个人是关键,只要其他99个人都出现在他前面(他防风看见99次灯亮),就可以了,但是他不能打亮灯,也就是说灯和他没关系,他只是观察者. 虽说概率小一点,但理论上行得通

mengduan · 发表于 2004-5-13 02:22:12

<

>楼上的老兄<

>你的办法好像不行呀 因为题上说的明白呢除非是放风的时候才能看到灯照你说的那个观察者是能看到灯了这不合要求呀

heyi · 发表于 2004-5-13 16:13:32

<

>上面的方法不是不符合要求，而是这样做可能要等到他的骨头都化了的时候才可以完成这个程序。所以必须寻找高效率的方法。

anlury · 发表于 2004-5-15 21:18:05

<

>可以这样不？没个人依次编上号码 1，2。3，…………，100<

>在放风的地方如果1去了后就做一个没个人都看的懂的记号说我1已经来了 <

>随后每个人放风是都留下对应的记号直到100为停止 注意到人说太多可以分成几个区来做分几个组 ~~估计可以出来了把

zwindling · 发表于 2004-5-23 18:20:33

想想看，好像很有点难。。。。

guaotian · 发表于 2004-7-20 19:16:55

<

>我人为可以用概率，起解决啊，<

>因为人是随机的，让所有人被抽出的概率趋近100就行了。

		自动登录	找回密码
密码			注-册-帐-号