寻找毒酒

来自计算思维百科
跳转至: 导航搜索
寻找毒酒1.png

有1000桶酒,其中1桶有毒。一旦吃了,毒性会在1周后发作。现在我们用小老鼠做实验,要在1周后找出那桶毒酒,问最少需要多少老鼠,如何检测?(老鼠的使用量越少越好,注意,毒性1周后才会发作,而且一周后必须出结果,所以时间紧迫)

解决方案—二进制法

我们最容易想到的办法就是1000只老鼠,每只老鼠喝一桶酒,最后哪只老鼠死了哪桶就是毒酒。这种方法的编号方式是十进制,从1~1000。虽然简单,但是因为1000桶中只有1桶有毒,却要耗费1000只老鼠,耗费量太大了。因此,我们可以考虑其他的编号方式。

首先把1000桶酒以10位二进制数分别标号,从0000000001至1111101000。因此只需要取10只老鼠,老鼠编码如下:

第一只 00000 00001

第二只 00000 00010

第三只 00000 00100

第四只 00000 01000

...

第十只 10000 00000

每只老鼠只喝其编码与酒编码做位与运算非0的酒。

0000000001      第一桶给第一只

0000000010      第二桶给第二只

0000000011      第三桶给第一、二只

0000000100      第四桶给第三只

0000000101      第五桶给第一、三只

1111101000      第一千桶给第四、六、七、八、九、十只

最后查看老鼠的死亡情况,记死亡为1,正常为0。如果毒酒的编码在某一位为1,则监控该位的老鼠必喝了,结果为1。即把10只老鼠的结果,按位填入一个10位二进制数中,其结果即为毒酒编号。

例如:编号为10001 00011的酒是毒酒。则对应的只有第一只,第二只,第六只,第十只死亡。

运用的计算思维

二进制的编号方式只需要10只老鼠,并且10只老鼠的结果都发挥了用处,直接推出了毒酒的编号。给老鼠编号的方式运用了“抽象” 的计算思维,将实物抽象成二进制数,方便后续的计算和推导。

参考链接

http://blog.csdn.net/wcyoot/article/details/6435906