【每天进步一点】毒药和老鼠的研究_.NET_编程开发_程序员俱乐部

之前碰到过毒药和老鼠，鸡蛋和称的问题，每次都拿笔在纸上推敲很久，这类问题今天终于有了完整的解决思路。

class="First">基础：

1.整数的二进制表达式

1000的二进制表达式是什么呢？

1000/2=500  --(余)--0
500/2=250   --(余)--0
250/2=125   --(余)--0
125/2=62    --(余)--1
62/2=31     --(余)--0
31/2=15     --(余)--1
15/2=7      --(余)--1
7/2=3       --(余)--1
3/2=1       --(余)--1
1/2=0       --(余)--1

1000的二进制表达式为 1111101000 = 2⁹ + 2⁸ + 2⁷ + 2⁶ + 2⁵ + 2³ = 512 + 256 + 128 + 64 +32 + 8

还需要其他的吗？不需要了，有上面的基础足矣。

二进制和上面的题目有什么关系呢？

在计算机基础里面，函数B2U_w表示Binary to Unsigned(长度为w的二进制到无符号整数)，它能够被定义为一个映射：

B2U_w{0,1}^w  --> {0,1,...,2^w-1}

也就是说表达0~2^w-1的整数值，只需要w位的二进制即可。

再转换一下：w位的二进制可以表达(2^w-1)+1=2^w个整数值。

反应在我们的命题中，n个瓶子对应n个可能的结果，转换成二进制之后，只需要x位的0101就可以表达出来了。(n已知，x未知。x的求值参考上面的结论)

出题：8瓶水，其中一瓶有毒，请问需要几只老鼠，如何测试呢？

步骤一：8 = (二进制)1000 = 2³。

即三位的二进制即可表达8种情况。

步骤二：将三位的二进制所有的情况罗列出来，剔除0的情况

计算机的整数(索引)从0开始，生活中的计数习惯从1开始，这里可以取个巧，将0理解为索引，映射到最后一个数字，在这里就是8；剔除0，也就是剔除了第8瓶水的情况。

┆  0  ┆  0  ┆  1 ┆  //1
┆  0  ┆  1  ┆  0 ┆  //2
┆  0  ┆  1  ┆  1 ┆  //3
┆  1  ┆  0  ┆  0 ┆  //4
┆  1  ┆  0  ┆  1 ┆  //5
┆  1  ┆  1  ┆  0 ┆  //6
┆  1  ┆  1  ┆  1 ┆  //7

从右往左，第一列对应的是1010101，其中1对应的数即为{1,3,5,7}；第二列对应0110011=>{2,3,6,7}；第三列对应0001111=>{4,5,6,7}

步骤三：提取上面的数字，得出结果。

第一只老鼠给他喂食(1,3,5,7)瓶水的混合液，第二只老鼠喂食(2,3,6,7)的混合液，第三只老鼠喂食(4,5,6,7)的混合液。

步骤四：根据结果推算答案。

如果第一只死了，第二只和第三只活着，我们依旧从右往左写成001(死掉为1，活着为0)，转成十进制整数为1。那么结论就是第1瓶水有毒。

如果第一只死了，第三只也死了，第二只活着。二进制为101，转十进制为5。那么结论就是第5瓶水有毒。

如果全部死亡。111，对应7，那么就是第7瓶水有毒。

如果全部存活。000，那就是0瓶水(或者容易理解的我们也说第8瓶水。计算机里的整数从0开始，而实际操作中从1开始。做这类题目的时候将0转换成最后一位即可)有毒。

步骤五：验证答案。

101的情况：第二只存活，说明2,3,6,7没有问题，而第一只和第三只，取他们的交集，有可能的是5和7，但是前面已经排除了7，所以答案是5。

再来验证110的情况：第一只存活，二、三只光荣了，说明1,3,5,7没问题，后两只的混合液取交集，有可能是6，7。前面排除了7，答案只能为6。

继续思考：

1000瓶水，找出其中有毒的那一瓶水，需要多少小白鼠，实际操作怎么样呢？

2⁹ < 1000 < 2¹⁰ 所以需要的白老鼠个数为10只，也就是10只老鼠才能充分的反应1000种情况。当然，10老鼠最多可以反映多少情况呢，应该是2¹⁰=1024种。

得出了需要十只老鼠，接下来十只老鼠应该怎么操作才能得出结论呢？

0000000001 ------1

0000000010 ------2

0000000011 ------3

0000000100 ------4

0000000101 ------5

...

1111100111 ------999

那么第一只老鼠应该喝1,3,5,7,9,11,...,997,999瓶水的混合液

第二只老鼠则是2,3,6,7,...,998,999瓶水的混合液

第三只老鼠则是4,5,6,7,12,13,14,15,...,996,997,998,999瓶水的混合液

...

第十只老鼠则是512,513,514,...,999瓶水的混合液

好吧，每个老鼠的指标都是接近500瓶的混合液，这也是自然的，每个位上有0,1两种可能。这么多，老鼠估计喝都喝死了。还想到一个问题啊，稀释这么严重，能毒死老鼠吗？这年头老鼠的生命力很顽强啊，这得上好的毒药啊......

......最后观察老鼠的牺牲情况，从右至左，死掉为1，活着为0，得到最终的二进制表达式，然后转换成十进制，即为有毒瓶子的答案。

注意：这里1000<2¹⁰的情况，也可以将1111101000 -----1000的情况列出来。最后如果第四、六七八九十只老鼠死了的话，就可以判断是第1000瓶水有毒。但是也可以将1000空出来，不喂食任何老鼠。最后没有老鼠死掉的话，也可以判断是第1000瓶水有毒了。这样可以避免老鼠的牺牲，阿弥陀佛~~~~

发散的问题：6个质量相等的小球和1个质量稍重的球，不能用天平，只能用称，设计一种方法，只能量三次就找出稍重的球。

类似的问题，这里数量变成了7个。测试数据也从死掉变成了重和轻，不过一样可以转换成0和1。

如果你看懂了上面，不妨想想这个的答案。