计算机和实际问题

一，知乎上的一个问题？

你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？

2^10 = 1024，很明显，这个问题是可解的。

1，直观的解法一：

将老鼠以二进制为 0000 0000 00 ， 一周后死置为1，没死为0。
将瓶子变为1-1000，十位二进制化，位置为1的说明该瓶水需要喂给该位置的老鼠。遍历所有水瓶，一周后得出结果。

2，方法论转化解法二：

其实在实际上，会有一个小问题？老鼠喝得了这么多水吗？（喝水最多的老鼠要接触500瓶水）。当然，这里是题目，不会有这种情况，只是刚好有网友提到了这个情况。实际上可能会遇到各种问题，因此拓宽解决问题思路很有意义。

那么其实这里在运用相同本质的原理上，可以进行转化的。
以水来做混合标记：比如 第2瓶 = 0000 0000 10，第3瓶= 0000 0000 11 可以看到，此处的第二位都是1，那么第2瓶和第3瓶，混合后喂给第2只老鼠即可，根据题目需要，我们可以预先调制出 10 瓶我们需要的溶液，依次喂给各个老鼠即可，然后根据老鼠的死亡情况即可得到有毒的瓶子标号。举一个简化例子如下： 14个 瓶子有一个瓶子有毒：

• 依解法一直接让每一瓶编号给对应需要的老鼠喝即可。比较简单不再写过程。
• 解法二详细如下：

瓶子1-14编号如下：
1：0001
2：0010
3：0011
4：0100
5：0101
6：0110
7：0111
8：1000
9：1001
10：1010
11：1011
12：1100
13：1101
14：1110
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

配置四瓶溶液，根据编号的二进制可以看到，配置的结果如下：

第一瓶：由 编号1，3，5，7，9，11，13 融合而成。
第二瓶：由 编号2，3，6，7，10，11，14 融合而成。
第三瓶：由编号4，5，6，7，12，13，14 融合而成。
第四瓶：由编号8，9，10，11，12，13，14 融合而成。
1
2
3
4

将溶液依次喂给老鼠，一周后即可得出结果。比如，如果是5号溶液有毒，那么结果是第1，3 只老鼠被毒死。第14号溶液有毒，那么第 2，3，4只老鼠被毒死。

3，二分法的运用：如改变一下预设条件，老鼠喝了毒水会立即死，或者，不再限制需要在一星期内找出毒水，即不限制找出毒水的时间或者毒水立即生效，但是要让损耗的原材料尽量少（老鼠和药水尽量少损耗）。如何做？

解法（以最高损耗为计算）：

• 药水分为两堆，一堆500，用一只老鼠试其中一堆的混合液，得到有毒的一堆

• 再将有毒药水分为两堆，一堆250，再用第二只试其中一堆的混合液，得到有毒的一堆

• 再将有毒药水分为两堆，一堆125，再用第三只试其中一堆的混合液，得到有毒的一堆

• 再将有毒药水分为两堆，一堆63，62，再用第四只试其中一堆的混合液，得到有毒的一堆

• 再将有毒药水分为两堆，一堆32，31，再用第五只试其中一堆的混合液，得到有毒的一堆

• 再将有毒药水分为两堆，一堆16，再用第六只试其中一堆的混合液，得到有毒的一堆

• 再将有毒药水分为两堆，一堆8，再用第七只试其中一堆的混合液，得到有毒的一堆

• 再将有毒药水分为两堆，一堆4，再用第八只试其中一堆的混合液，得到有毒的一堆

• 再将有毒药水分为两堆，一堆2，再用第九只试其中一堆的混合液，得到有毒的一堆

• 再将有毒药水分为两堆，一堆1，再用第十只试其中一堆的混合液，得到有毒的一堆

可以发现，在最差的情况下，我们损耗了十只老鼠，但每一次测试一直减少正常药水的消耗，保留许多完好的药水（有一半的药水只需要用0或1次，用的最多的药水也只是10次）。

而在实际情况下，我们其实没有这么好的运气每次都能测试到有毒的一堆，那么老鼠可以进行重复测试。而至少有一般的药水只需要用到1次以下，一瓶药水最多只需要使用10次，减少了原材料损耗。