这个不行，你相当于用了两个bits的信息，来表达题目要求的一个bit的信息，这个应该是玩赖，我的答案可以保证99个人

这个不行，你相当于用了两个bits的信息，来表达题目要求的一个bit的信息，这个应该是玩赖。

作为脑筋急转弯是可以（还可一拖长声音，按拍数传递更多信息），但是如果是计算机算法题，你这个不是正确答案。

我的答案可以保证99个人活下来。

最起码，如果知道一个压缩算法（比如压缩率33.3%），最起码成保证2/3的人活下来，（其余的三分之一，作为压缩结果）

但是如果利用奇偶校验的办法，我可以保证99个人活下来。

最后一个人，如果蓝帽子是奇数，那么他就说是蓝帽子。他的成活概率50%。

倒数第二个人，根据倒数第一个人说的信息（蓝帽子是奇数），加上他自己看到的前边蓝帽子的奇偶数，可以判断出自己的帽子颜色。成活率 100%

除了倒数第一个人，每个人都知道前99个人蓝帽子的奇偶信息（由倒数第一个人提供的）。还知道自己后边每个人的颜色（因为他们自己已经说了。），还知道自己之前每个人的颜色（这个人自己看到的），也就能算出来自己的颜色了。所以成活率是100%。

总的来说，保证99个人成活。

所有跟帖： 

• 我的答案可以保证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