设万维读者为首页 广告服务 联系我们 关于万维
简体 繁体 手机版
分类广告
版主:阿飞的剑
万维读者网 > 茗香茶语 > 帖子
粱远声:囚徒问题一个较好的解
送交者: 粱远声 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 次时,宣布所有人都放过风了。

0%(0)
0%(0)
标 题 (必选项):
内 容 (选填项):
实用资讯
回国机票$360起 | 商务舱省$200 | 全球最佳航空公司出炉:海航获五星
海外华人福利!在线看陈建斌《三叉戟》热血归回 豪情筑梦 高清免费看 无地区限制
一周点击热帖 更多>>
一周回复热帖
历史上的今天:回复热帖
2008: 青年时代的奥先知,帅照一张祝茶童鞋圣
2008: ZT: BBC中国听众:我现在非常拥护共产
2007: 加拿大,你们的技术移民怎么啦?
2007: 体验深圳(2)-劳动密集型产业
2006: 木头谈酒(2)-喝啤酒
2006: 6-4,波士顿城外槐花香(职业本人图)
2005: 莲花落(续四)
2005: 已经没人会说满话了....
2004: 对杨振宁祖孙配现象的思考
2004: 对点小二及其他网友的回复