紅藍帽子問題的真正答案

來源: a7a8 於 2011-12-11 14:48:38 [] [舊帖] [給我悄悄話] 閱讀數 : (919 bytes)
本文內容已被 [ a7a8 ] 在 2011-12-12 02:34:33 編輯過。如有問題，請報告版主或論壇管理刪除.

這是一個二元邏輯問題。關鍵在於邏輯等式 非對 = 錯。

應用到本題即 非紅 = 藍

囚犯1運氣最差,必需猜測自己帽子的顏色。僅有50%生存機會。他在回答自己帽子顏色的同時要讓囚犯2知道其帽子顏色。

比如,囚犯1猜測自己帽子是紅色, 而他看到囚犯2帽子顏色為紅色, 責他可以說“我的帽子是紅色”。其意味是兩帽子都是紅色。

如果他看到囚犯2帽子顏色為藍色，責他可以說“我的帽子不是藍色”。其意味是自己帽子是紅色，而下麵一位的帽子是藍色。

如此相傳，餘下99個囚犯均能安全獲救.

此題的陷阱在給出了充分不必要條件 - 每個囚犯能看到過多的帽子。所以有人給出計算奇偶數的解法,並受到一小撮人追捧.從算法可執行性角度這是不可取的.囚犯要經過大量計算才能保命,但是不是每個囚犯都是數學好的.如果放大計算難度，1000名囚犯,則這個算法僅僅理論可行,而不具備實踐意義。

從計算科學角度分析,我給出的算法複雜度（O（N））低並且保持穩定效能.而後者是O（N*N）的複雜度.

所有跟帖： 

• 牛 -滿地找牙- ♂ 給 滿地找牙 發送悄悄話 滿地找牙 的博客首頁 (0 bytes) () 12/11/2011 postreply 15:18:30

• You made an assumption that they can say "我的帽子不是藍色". -股市一豬- ♂ 給 股市一豬 發送悄悄話 (49 bytes) () 12/11/2011 postreply 15:51:40

• 在這種情況下，他們可以考慮用東北和湖南口音來說～～～ -e帶漸寬- ♂ 給 e帶漸寬 發送悄悄話 e帶漸寬 的博客首頁 (0 bytes) () 12/11/2011 postreply 16:01:13

• 這個牛！ -股市一豬- ♂ 給 股市一豬 發送悄悄話 (0 bytes) () 12/11/2011 postreply 16:11:45

• 回複：You made an assumption that they can say "我的帽子不是藍色". -a7a8- ♀ 給 a7a8 發送悄悄話 (143 bytes) () 12/11/2011 postreply 16:22:59

• 用red和reeed;blue和bluuue來區分唄~ --笑笑-- ♀ 給 -笑笑- 發送悄悄話 -笑笑- 的博客首頁 (0 bytes) () 12/12/2011 postreply 07:08:25

• 幾點補充：這是數學問題 -a7a8- ♀ 給 a7a8 發送悄悄話 (160 bytes) () 12/11/2011 postreply 17:05:36

• 回複：紅藍帽子問題的真正答案 -math1999- ♀ 給 math1999 發送悄悄話 (19671 bytes) () 12/11/2011 postreply 17:18:40

• 你不能假設帽子，那是國王的權力。此題是囚犯自救。 -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/11/2011 postreply 18:42:33

• 這個不行，你相當於用了兩個bits的信息，來表達題目要求的一個bit的信息，這個應該是玩賴，我的答案可以保證99個人 -612309- ♀ 給 612309 發送悄悄話 612309 的博客首頁 (906 bytes) () 12/11/2011 postreply 18:46:16

• 我的答案可以保證99個人. 見前post -612309- ♀ 給 612309 發送悄悄話 612309 的博客首頁 (0 bytes) () 12/11/2011 postreply 18:47:59

• 不存在玩賴問題。不是非要一個BIT，算法最優是思路。 -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/11/2011 postreply 19:01:52

• 如果你碰巧最後一個回答問題，假設隊伍10000人，你保證崩潰 -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/11/2011 postreply 19:03:10

• 如果你是計算機專業，我替你慚愧；如果你不是計算機專業，不和你爭。 -612309- ♀ 給 612309 發送悄悄話 612309 的博客首頁 (0 bytes) () 12/11/2011 postreply 19:12:09

• 在已知下一計算節點狀態時不傳結果反而傳參數去計算。難得一笑。 -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/11/2011 postreply 19:28:14

• 不入你和我都把算法寫出來，比算法較複雜度定優劣。 -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/11/2011 postreply 19:31:50

• 時間複雜度我的是O(n), 空間複雜度也是O(n). -612309- ♀ 給 612309 發送悄悄話 612309 的博客首頁 (322 bytes) () 12/11/2011 postreply 19:53:52

• 其實，我的空間複雜度隻是O(1)而已. -612309- ♀ 給 612309 發送悄悄話 612309 的博客首頁 (109 bytes) () 12/11/2011 postreply 20:00:30

• 單個結點需要遞歸前麵所有結點的結果, 是NX(N-1), 全部結點複雜度O(n^3) -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/12/2011 postreply 06:08:55

• 更正一下,單個結點因為遞歸所有前麵結點,複雜度為∑N! -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/12/2011 postreply 06:55:46

• 再次重申，這是典型離散數學問題。家有高中生的可以試試他的計算機天賦。 -a7a8- ♀ 給 a7a8 發送悄悄話 (187 bytes) () 12/11/2011 postreply 19:10:41

• 既如此,國王又沒規定不許說啥,那就用某同學給的方子唄:我的是X色前麵是X色.搞定!至少99.5%. -笑比哭好- ♀ 給 笑比哭好 發送悄悄話 笑比哭好 的博客首頁 (107 bytes) () 12/12/2011 postreply 02:39:06

• "現國王要求從最後一個開始報自己頭頂上帽子的顏色，報對就能活著" -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/12/2011 postreply 06:02:38

• 噢.是有這句. --笑笑-- ♀ 給 -笑笑- 發送悄悄話 -笑笑- 的博客首頁 (0 bytes) () 12/12/2011 postreply 07:00:22

• 此題國內有一本<趣味數學300題>收錄,還有一問. -a7a8- ♀ 給 a7a8 發送悄悄話 (478 bytes) () 12/12/2011 postreply 06:25:26

• 130的不帶醬紫翹尾巴滴~~~ --笑笑-- ♀ 給 -笑笑- 發送悄悄話 -笑笑- 的博客首頁 (0 bytes) () 12/12/2011 postreply 07:04:05

• 你的智商250. -612309- ♀ 給 612309 發送悄悄話 612309 的博客首頁 (0 bytes) () 12/12/2011 postreply 10:58:35

• 過獎,過獎,達芬奇才是250. -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/12/2011 postreply 11:30:20

• 你的算法時間複雜度無法達到O(n), n個結點,每個結點必須根據所有下級結點結果計算,最好成績O(n^2), -a7a8- ♀ 給 a7a8 發送悄悄話 (25 bytes) () 12/12/2011 postreply 12:16:37

• 你偷偷放入了一個不能用的假設 -藍莓餡餅- ♂ 給 藍莓餡餅 發送悄悄話 藍莓餡餅 的博客首頁 (231 bytes) () 12/12/2011 postreply 23:04:32

• 再多說一點：你的答案放入了額外的信息，並不隻是“紅”“藍” -藍莓餡餅- ♂ 給 藍莓餡餅 發送悄悄話 藍莓餡餅 的博客首頁 (256 bytes) () 12/12/2011 postreply 23:23:27

• 約定第一個報偶數的顏色難道不是共同約定?還得通過更複雜方法解碼! -a7a8- ♀ 給 a7a8 發送悄悄話 (989 bytes) () 12/13/2011 postreply 06:35:40

• 隻要你認為有protocal就有解就行。沒人不服氣，隻要不說“正解”就好了。 -藍莓餡餅- ♂ 給 藍莓餡餅 發送悄悄話 藍莓餡餅 的博客首頁 (77 bytes) () 12/13/2011 postreply 10:21:09

• 不說正解能把你吸引來看? -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/13/2011 postreply 10:33:20

• 智商高低不要緊，要謙虛。下麵是標準答案 -uulemon- ♂ 給 uulemon 發送悄悄話 (1298 bytes) () 12/13/2011 postreply 15:43:29

• 您的所謂標準答案敢情是某網站扒來的,有點自己的貨沒有?別怪我不謙虛,你能理解的高度比他們差太遠 -a7a8- ♀ 給 a7a8 發送悄悄話 (0 bytes) () 12/13/2011 postreply 17:27:30

• 這個是考數學和邏輯能力，不是靠作弊能力。 -uulemon- ♂ 給 uulemon 發送悄悄話 (57 bytes) () 12/13/2011 postreply 15:46:06

• 找到原文了,二手信息漏洞多. -a7a8- ♀ 給 a7a8 發送悄悄話 (1852 bytes) () 12/13/2011 postreply 18:55:18

• 我的答案可以推廣至三種以上顏色 -走過路過千萬不要錯過- ♀ 給 走過路過千萬不要錯過 發送悄悄話 (824 bytes) () 12/15/2011 postreply 13:32:29

請您先登陸，再發跟帖！