設萬維讀者為首頁 廣告服務 技術服務 聯繫我們 關於萬維
簡體 繁體 手機版
分類廣告
版主:阿飛的劍
萬維讀者網 > 茗香茶語 > 帖子
粱遠聲:囚徒問題一個較好的解
送交者: 粱遠聲 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: 對點小二及其他網友的回覆