這個不行，你相當於用了兩個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