經典面試題：1000瓶水1瓶毒藥，10隻老鼠1天如何測出毒瓶？

經典面試題：1000瓶水1瓶毒藥，10隻老鼠1天如何測出毒瓶？

核心洞察：2^10 = 1024 > 1000，10 隻老鼠可構成 10 位二進制，足以編碼 1000 種狀態。

操作步驟

1. 將 1000 瓶水編號 1~1000，轉為 10 位二進制（不足位補 0）。
2. 10 隻老鼠排成一排，對應二進制位（第 1 位 ~ 第 10 位）。
3. 對於編號 k 的水瓶，其二進制第 i 位為 1，則讓第 i 隻老鼠喝一滴。
4. 24 小時後觀察：死亡老鼠位 = 1，存活 = 0，組成 10 位二進制數，即為毒水瓶編號。

範例

瓶號 3 = 0000000011 → 第 1、2 隻老鼠喝。
瓶號 1000 = 1111101000 → 第 4、6、7、8、9、10 隻喝。

代碼模擬（驗證邏輯）

#include <stdio.h>
int main() {
    int poison = 847; // 假設毒瓶
    int dead = 0;
    for (int i = 0; i < 10; i++) {
        if (poison & (1 << i)) dead |= (1 << i); // 第 i 隻死
    }
    printf("毒瓶編號：%d\n", dead); // 輸出 847
    return 0;
}

延伸思考

• 若有 m 隻老鼠、t 輪測試，可檢測 (t+1)^m 瓶（每輪老鼠可喝/不喝/死/活多狀態）。
• 實際生物實驗需考慮劑量、稀釋、統計顯著性等工程細節。