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

[转帖]100囚徒难题

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

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

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

难，想

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

的确很难，正在想。

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

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

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

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

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

<P>楼上的老兄</P><P>你的办法好像不行呀<FONT size=1>   </FONT><FONT face="" size=3>因为题上说的明白呢   除非是放风的时候才能看到灯   照你说的那个观察者是能看到灯了   这不合要求呀</FONT></P>

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

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

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

<P>可以这样不 ？没个人依次编上号码1，2。3，…………，100</P><P>在放风的地方如果1去了后 就做一个没个人都看的懂的记号 说我1已经来了 </P><P>随后每个人放风是都留下对应的记号   直到100为停止</P><P>注意到人说太多 可以分成几个区 来做分几个组 ~~估计可以出来了 把</P>

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

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

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

<P>我人为可以用概率，起解决啊，</P><P>因为人是随机的，让所有人被抽出的概率趋近100就行了。</P>
页: [1] 2 3 4 5 6 7
查看完整版本: [转帖]100囚徒难题