红蓝帽子问题的真正答案

这是一个二元逻辑问题。关键在于逻辑等式 非对 = 错。

应用到本题即 非红 = 蓝

囚犯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带渐宽- ♂ (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- ♀ (143 bytes) () 12/11/2011 postreply 16:22:59

• 用red和reeed;blue和bluuue来区分呗~ --笑笑-- ♀ (0 bytes) () 12/12/2011 postreply 07:08:25

• 几点补充：这是数学问题 -a7a8- ♀ (160 bytes) () 12/11/2011 postreply 17:05:36

• 回复：红蓝帽子问题的真正答案 -math1999- ♀ (19671 bytes) () 12/11/2011 postreply 17:18:40

• 你不能假设帽子，那是国王的权力。此题是囚犯自救。 -a7a8- ♀ (0 bytes) () 12/11/2011 postreply 18:42:33

• 这个不行，你相当于用了两个bits的信息，来表达题目要求的一个bit的信息，这个应该是玩赖，我的答案可以保证99个人 -612309- ♀ (906 bytes) () 12/11/2011 postreply 18:46:16

• 我的答案可以保证99个人. 见前post -612309- ♀ (0 bytes) () 12/11/2011 postreply 18:47:59

• 不存在玩赖问题。不是非要一个BIT，算法最优是思路。 -a7a8- ♀ (0 bytes) () 12/11/2011 postreply 19:01:52

• 如果你碰巧最后一个回答问题，假设队伍10000人，你保证崩溃 -a7a8- ♀ (0 bytes) () 12/11/2011 postreply 19:03:10

• 如果你是计算机专业，我替你惭愧；如果你不是计算机专业，不和你争。 -612309- ♀ (0 bytes) () 12/11/2011 postreply 19:12:09

• 在已知下一计算节点状态时不传结果反而传参数去计算。难得一笑。 -a7a8- ♀ (0 bytes) () 12/11/2011 postreply 19:28:14

• 不入你和我都把算法写出来，比算法较复杂度定优劣。 -a7a8- ♀ (0 bytes) () 12/11/2011 postreply 19:31:50

• 时间复杂度我的是O(n), 空间复杂度也是O(n). -612309- ♀ (322 bytes) () 12/11/2011 postreply 19:53:52

• 其实，我的空间复杂度只是O(1)而已. -612309- ♀ (109 bytes) () 12/11/2011 postreply 20:00:30

• 单个结点需要递归前面所有结点的结果, 是NX(N-1), 全部结点复杂度O(n^3) -a7a8- ♀ (0 bytes) () 12/12/2011 postreply 06:08:55

• 更正一下,单个结点因为递归所有前面结点,复杂度为∑N! -a7a8- ♀ (0 bytes) () 12/12/2011 postreply 06:55:46

• 再次重申，这是典型离散数学问题。家有高中生的可以试试他的计算机天赋。 -a7a8- ♀ (187 bytes) () 12/11/2011 postreply 19:10:41

• 既如此,国王又没规定不许说啥,那就用某同学给的方子呗:我的是X色前面是X色.搞定!至少99.5%. -笑比哭好- ♀ (107 bytes) () 12/12/2011 postreply 02:39:06

• "现国王要求从最后一个开始报自己头顶上帽子的颜色，报对就能活着" -a7a8- ♀ (0 bytes) () 12/12/2011 postreply 06:02:38

• 噢.是有这句. --笑笑-- ♀ (0 bytes) () 12/12/2011 postreply 07:00:22

• 此题国内有一本<趣味数学300题>收录,还有一问. -a7a8- ♀ (478 bytes) () 12/12/2011 postreply 06:25:26

• 130的不带酱紫翘尾巴滴~~~ --笑笑-- ♀ (0 bytes) () 12/12/2011 postreply 07:04:05

• 你的智商250. -612309- ♀ (0 bytes) () 12/12/2011 postreply 10:58:35

• 过奖,过奖,达芬奇才是250. -a7a8- ♀ (0 bytes) () 12/12/2011 postreply 11:30:20

• 你的算法时间复杂度无法达到O(n), n个结点,每个结点必须根据所有下级结点结果计算,最好成绩O(n^2), -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- ♀ (989 bytes) () 12/13/2011 postreply 06:35:40

• 只要你认为有protocal就有解就行。没人不服气，只要不说“正解”就好了。 -蓝莓馅饼- ♂ (77 bytes) () 12/13/2011 postreply 10:21:09

• 不说正解能把你吸引来看? -a7a8- ♀ (0 bytes) () 12/13/2011 postreply 10:33:20

• 智商高低不要紧，要谦虚。下面是标准答案 -uulemon- ♂ (1298 bytes) () 12/13/2011 postreply 15:43:29

• 您的所谓标准答案敢情是某网站扒来的,有点自己的货没有?别怪我不谦虚,你能理解的高度比他们差太远 -a7a8- ♀ (0 bytes) () 12/13/2011 postreply 17:27:30

• 这个是考数学和逻辑能力，不是靠作弊能力。 -uulemon- ♂ (57 bytes) () 12/13/2011 postreply 15:46:06

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

• 我的答案可以推广至三种以上颜色 -走过路过千万不要错过- ♀ (824 bytes) () 12/15/2011 postreply 13:32:29