1.1 趣味故事：用小白鼠檢驗毒水瓶

學習計算機，首先要學習計算思維。那什么是計算思維呢？首先看一個問題及其求解，這個問題不需要很多數學知識，所有讀者都應能求解。

示例1　問題：有1 000瓶水，其中一瓶是有毒的，小白鼠只要嘗一點帶毒的水，24小時內就會死亡，問：至少要有多少只小白鼠才能在24小時內檢驗出哪瓶水有毒？怎樣檢驗？

看下面的求解過程，如圖1.1所示。

圖1.1　“用小白鼠檢驗毒水瓶”問題求解示意

第1步，將1 000瓶水逐瓶編號，編號從0～999，假設第997號瓶水有毒。

僅用十進制編號，很難看出如何求解。怎么做呢？可以用二進制求解該題。

第2步，做一個變換，將每瓶水的編號由十進制轉換為二進制。

1位二進制數只能表示0或1（最大編號21-1），2位二進制數能表示0～3（最大編號22-1），……，以此類推，10位二進制數能表示0～1 023（最大編號210-1）。因此，若要表示999這個編號，則需要10位二進制數。由此，是否可想到需要10只小白鼠就可在24小時內檢驗出哪瓶水有毒呢？

答案是10只。問題接著來了：應該怎樣讓小白鼠喝水，才能用10只小白鼠的存亡狀態，從1 000瓶水中判斷出哪一瓶有毒呢？注意：小白鼠喝了有毒的水，可能很快死亡，但也可能在接近24小時時死亡，因此不能一只一只地試驗，那樣時間不夠。

第3步，每一瓶水的編號都是10位二進制數，記為B9B8B7B6B5B4B3B2B1B0（其中Bi僅為0或1，i=0，…，9），10只小白鼠分別編號為M9，M8，M7，M6，M5，M4，M3，M2，M1，M0。制定規則如下：編號為B9B8B7B6B5B4B3B2B1B0的一瓶水，如果Bi位為1，則讓Mi小白鼠喝一口；如果Bi位為0，則不讓Mi小白鼠喝。

第4步，1 000瓶水，均按上述規則進行處理。待小白鼠喝完后，靜等24小時，然后看哪只小白鼠死掉了。如Mi小白鼠死了，則Mi=1，否則Mi=0。將Mi連起來看，依題，M9M8M7M6M5M4M3M2M1M0=1111100101，就得出了有毒水瓶的二進制編號，再還原回十進制編號，便可知道997號瓶的水有毒。