例題 3.1：分割黃金問題（MS）#

題目#

泰勒是一位房主，僱用鮑尼為自己新建的房子鋪設院子裡的地磚，這是一個七天工作量的活兒。泰勒答應一共支付一根金條作為報酬，但鮑尼要求每天支付他 1/7 的工資。請問如何在金條上切兩刀，保證每天正好能支付鮑尼 1/7 的工資？

解題思路#

• 大部分失敗者試圖把金條切成等質量的七份，但對於長方體，無論怎樣平著切兩刀都只能分出四份
• 關鍵是在拿到題目之前，不要一心想著怎麼「動刀」，而是想想為什麼計算機公司會考這道題——這個問題和計算思維應該有些關聯

答案#

• 在金條 1/7 的地方切一刀，在 3/7 的地方再切一刀，得到三個小金塊，質量分別為 1/7、2/7 和 4/7
• 用 1、2、4 這三個數字可以表示 1 ～ 7 的所有數字：

與二進制的關係#

• 1、2、4 分別是二進制的「個位數」「十位數」和「百位數」
• 因為二進制只有 0、1 兩個數字，每一個進位是 0 或者是 1 的組合，就能表示各種數字
• 這道例題考查的是計算機從業者對二進制編碼的理解程度，以及靈活應用二進制編碼解決實際問題的能力

例題 3.2：小白鼠試驗問題（AB）#

題目#

有 64 瓶藥，其中 63 瓶是無毒的，一瓶是有毒的。如果做試驗的小白鼠喝了有毒的藥，三天後會死亡。現在只剩下三天時間，一只小白鼠只能參與一次試驗，請問最少需要多少只小白鼠才能試出哪瓶藥有毒？

直覺答案 vs. 正確答案#

• 很多人直覺回答 64 只，每一只吃一種不同的藥——這可以做到但並非最優
• 正確答案：只需要 6 只小白鼠

解題方法#

1. 首先將 64 瓶藥從 0 到 63 按二進制編號，即從 000000 到 111111
2. 選六只小白鼠從左到右排開，和二進制的各個位置對應
3. 每一只小白鼠吃表格中相應列所對應的二進制是 1 的藥
4. 三天後觀察哪些小白鼠死了，死了的對應位置為 1，活著的為 0，組成的二進制數就是有毒藥瓶的編號

信息論的解釋#

• 64 選 1 的任務，從理論上講只需要 log64 = 6 比特的信息
• 每一只小白鼠在試驗後有兩個結局（活或死），提供了 1 比特信息
• 因此從理論上講六只小白鼠就足夠了

這是先從理論上找到編碼的長度，再設計編碼方法。這道題除了能測試一個人對二進制編碼的理解之外，還能測試一個計算機科學家是否懂得如何做試驗、做研究。

A/B 測試與編碼的延伸#

• 今天很多計算機產品需要通過用戶反饋來檢驗，通常做法是隨機選取 1% 的用戶做對比試驗（A/B 測試）
• 為了同時進行多個試驗，可以採用類似小白鼠試毒藥的方法，將不會發生衝突的試驗用二進制編碼，幾組試驗放在一起同時進行
• 一個資深工程師能靈活運用編碼原理解決整個公司層面的問題，就有了成為三級工程師的潛力

要點#

• 任何對象都可以通過對它們編號來區分，而任何的編號方法都等價於二進制編碼
• 給定一個集合，如何輸出它的冪集合？——一種好的方法是對冪集中的所有元素統一編碼