粱遠聲:囚徒問題一個較好的解 |
送交者: 粱遠聲 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 次時,宣布所有人都放過風了。 |
|
|
|
實用資訊 | |
|
|
一周點擊熱帖 | 更多>> |
|
|
一周回復熱帖 |
|
|
歷史上的今天:回復熱帖 |
2008: | 青年時代的奧先知,帥照一張祝茶童鞋聖 | |
2008: | ZT: BBC中國聽眾:我現在非常擁護共產 | |
2007: | 加拿大,你們的技術移民怎麼啦? | |
2007: | 體驗深圳(2)-勞動密集型產業 | |
2006: | 木頭談酒(2)-喝啤酒 | |
2006: | 6-4,波士頓城外槐花香(職業本人圖) | |
2005: | 蓮花落(續四) | |
2005: | 已經沒人會說滿話了.... | |
2004: | 對楊振寧祖孫配現象的思考 | |
2004: | 對點小二及其他網友的回覆 | |