經典算法面試題：1000瓶水1瓶毒，10只老鼠1天如何精準找出毒水？

問題：1000瓶水，1瓶有毒。老鼠喝毒水24小時後死亡。現有10只老鼠，如何在1天內確定哪瓶是毒水？

核心洞察：二進制編碼

2^10 = 1024 > 1000 → 10只老鼠的生/死狀態可編碼1024種情況，足夠覆蓋1000瓶水。

具體操作步驟

1. 給1000瓶水編號1~1000
2. 10只老鼠排成一排，從右向左對應二進制位（第1只=最低位，第10只=最高位）
3. 每瓶水按編號的二進制位決定哪些老鼠喝：
   • 第1瓶（二進制0000000001） → 第1只喝
   • 第2瓶（0000000010） → 第2只喝
   • 第3瓶（0000000011） → 第1、2只喝
   • 第4瓶（0000000100） → 第3只喝
   • ...
   • 第1000瓶（1111101000） → 第4、6、7、8、9、10只喝
4. 24小時後觀察：死=1，活=0
5. 將10只老鼠生死狀態組成10位二進制數，轉為十進制 → 即毒水編號

舉例驗證

若第13瓶是毒水（二進制0000001101）→ 第1、3、4只老鼠喝了毒水 → 24小時後這3只死，其餘活 → 讀取二進制0000001101 = 13 → 精準定位。

算法本質

這是非自適應分組測試的經典應用：
• 每只老鼠 = 1 bit信息
• 10 bit可區分1024種可能
• 一次性並行測試，時間最優（1天）

變體思考

• 若有2天時間 → 可用自適應策略，老鼠更少（二分法）
• 若老鼠喝毒水立即死 → 可順序測試，但時間受限
• 擴展到多瓶毒水 → 需組合數學/纠錯碼

這道題考察信息論思維與二進制編碼靈活運用，是面試中極具區分度的經典好題。