問題描述

有1000瓶水，其中有1瓶是有毒的。小白鼠喝了有毒的水之后24個小時就會死亡，問最少需要多少只小白鼠進行實驗，才能在24小時內檢測出哪瓶水有毒？

問題分析

如果沒有時間限制的話，我們只要讓一只小白鼠依次喝每瓶水就行了，隔24小時看它死沒死，如果死了，那剛喝的這瓶就是有毒的，如果沒死，就喝下一瓶。

問題是有時間限制，24小時內就要檢測出哪瓶有毒。

1000這個數字太大了，我們可以從小一點的情況開始考慮。

比如說，有兩瓶水，其中一瓶是有毒的。這個時候我們只需要一只小白鼠就行了，讓它喝下其中一瓶水，24小時后，如果小白鼠死了，那么喝的這瓶就是有毒的，如果沒死，那么另外一瓶就是有毒的。

現在我們用數學模型的方式來描述一下這個過程。

我們現在是要得到一只小白鼠到一瓶有毒的水的對應關系，即用24小時后小白鼠的不同狀態來編碼不同的水。24小時后小白鼠只有兩種狀態，活著或者死了。我們用0表示活著，1表示死了。因為只有一只小白鼠，所以狀態編碼只有1位，即：

一只小白鼠狀態編碼

小白鼠狀態	活著	死了
小白鼠狀態編碼	0	1

?

如果我們給兩瓶水分別標號0和1，而讓小白鼠喝標號為1的那瓶水，這個時候如果小白鼠死了，那么也就意味著標號為1的那瓶水是有毒的，而小白鼠此時的狀態編碼無疑就是1 ！而如果小白鼠沒死，那么就意味著標號為0的那瓶水時有毒的，而小白鼠此時的狀態編碼無疑就是0 ！

理清一下，我們只要把標號為1的水給小白鼠喝，標號為0的說不給小白鼠喝，那么24小時后小白鼠的狀態編碼就是有毒的水的編號，因此找到了有毒的水。

小白鼠只有一只，相當于其狀態編碼只有1位，而要編碼兩瓶水，確實只需要1個二進制位就夠了。

現在考慮更復雜一點的情況。

如果有4瓶水，需要幾只小白鼠？

兩瓶水需要1個二進制位就夠了，那么4瓶水需要2個二進制位就夠了。

即 00 01 10 11四種編碼，分別對應十進制0 1 2 3。

兩個二進制位中，第一位代表第一只小白鼠的喝水情況，第二位代表第二支小白鼠的喝水情況。

即00，表示對于標號為0的水來說，既不給第一只小白鼠喝，也不給第二只小白鼠喝。

01，表示標號為1的水，不給第一只小白鼠喝，但是給第2只小白鼠喝。

10，表示標號為2的水，給第一只小白鼠喝，不給第二只小白鼠喝。

11，表示標號為3的水，既給第一只小白鼠喝，也給第二只小白鼠喝。

注意了，我們給4瓶水分別編號 0 1 2 3，換算成二進制，00 01 10 11，這四個編碼有兩個方向的含義：

? ? ? ? 一個是從水到小白鼠的，即某瓶水對應的2位二進制編碼，位 i (i = 0 或 1)代表了這瓶水要不要給第 i 只小白鼠喝。

? ? ? ? 一個是從小白鼠到水的，即兩只小白鼠代表兩個二進制位，其死（1）活（0）就代表那一位上的值，如果第一只小白鼠死了，那么第一位就是1否則為0，第二只則對應了第二位。

因此我們把四瓶水按照它們對應的編碼分別喂給對應的小白鼠，最后小白鼠的狀態編碼就能標識出這四瓶水中哪一瓶是有毒的。

比如狀態編碼是 00，即兩只小白鼠都活著，但是我們看一開始給小白鼠喂水的情況可得：

第一只小白鼠喝了第 2瓶水和第3瓶水，但是它還活著也就是說第2，3瓶水沒毒呀。

第二只小白鼠喝了第1瓶水和第3瓶水，也就是說第1，3瓶水沒毒。

于是有毒的水就是第 0 瓶，剛好對應上兩只小白鼠最后的狀態編碼 00 ，十進制0。

再復雜一點，如果有8瓶水，分別標號 0 1 2 3 4 5 6 7 8?

對應二進制編碼為 000 001 010 011 100 101 110 111

每瓶水都對應了3個二進制位，可以認為是給三只小白鼠的喂水情況，還是某一位是1的話就給某個小白鼠喂水，是0就不喂。

依次把8瓶水按其編碼給對應小白鼠喂水，24小時后3只小白鼠的生死狀況會得到一個3位的二進制編碼，其于有毒的那瓶水的標號二進制編碼相同，即找到了有毒的那瓶水。

?

由此我們可以得到規律，如果有y瓶水，要找到其中一瓶有毒的，最少需要x只小白鼠來試讀，只需要 2^x > y 即可，即x個二進制位能夠完全編碼y瓶水。

因此 2^9 = 512 < 1000 < 2^10

因為9只小白鼠無法編碼1000瓶水，因此最少需要10只小白鼠。

具體操作方法就是給這1000瓶水分別標號0到999，將其標號轉換為10位二進制數，如果某瓶水對應10位二進制數的第i位為1，那么就把這瓶水讓第i只小白鼠喝一口。24小時后，10只小白鼠的生死狀態組成了一個10位二進制數，這個10位二進制數對應的那瓶水有毒。

?

?

?

?

?

?

?

?

總結

以上是生活随笔為你收集整理的智力题------小白鼠试毒问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。