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位二进制数，记为B9B 8B 7B 6B5B 4B 3B 2B 1B 0（其中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号瓶的水有毒。