利用 Python 解决“老鼠喝药水”问题

前言

我在互联网上高强度冲浪的时候，偶然发现了这个问题，终于在经过 OI 大神指点下，在CSDN帮助下，想到了解决方法。

题目

你的面前有 100 瓶打乱了的药水，其中有且只有一瓶为毒药. 你有 7 只老鼠，喝了毒药的老鼠会死去，反之不会. 现请你利用这 7 只老鼠设计一种方案，根据老鼠的死活情况找出毒药.

假定每只老鼠可以喝下无限量的药水，且每瓶药水不会被喝完. 在方案实施的过程中，你无法得知当前的执行情况，也就是说，你不能根据前一只老鼠的死活决定后续的操作.

困难

这个问题中，最困难的是，我们需要进行完所有步骤以后，才能得知结果，无法根据前一只老鼠的死活决定后续操作。

在和同学讨论的过程中，大家都偏向于使用二分法，不断逼近，且不考虑上面的困难，就单论二分法来讲，我们很可能在七只老鼠都死完之后都找不到那杯药水。

这个时候，以我们目前高中的常规数学方法，已经无法解答这道题了，那怎么办？

二进制法

二进制是计算机的语言，让我们来粗略了解一下二进制。

我们平时使用的是十进制，即逢10进1，当我们写到第十一个数的时候是11，而不是别的，就如十六进制第十一个数使用了 a 来表示，二进制同理，逢2进1，写到第三个数时，二进制使用 11 来表示。

001 # 1
002 # 2
011 # 3
100 # 4
101 # 5

#后为十进制数，#前为二进制数，采用三位数的对齐方法，1 左边的数如果为0则没有实际意义。

了解了二进制，我们来再次审题，7只老鼠，100瓶药水，使用 Python 编写了二进制转换算法，列出了1到100所有数的二进制。

x=0
for i in range(0,100):
    x=x+1
    y = x
    b=""
    while(y>=1):
        b=str(num%2)+b
        num=num//2
    print(b)

我们发现，100的二进制转化结果 1100100 恰好就是一个七位数，这意味着 100 以前的数其二进制表示形式的数字位数永远不可能超过七，并且每个十进制数，只对应一个二进制数，正好我们有7只老鼠，我们可以利用这个特性来解决这个问题。

从左到右七个数，每个数对应一个老鼠，当它对应的那一位数为 1 时，就要喝下这瓶药水，假如喝第35瓶药水，那么我们先算出35所对应的二进制，并使用七位数对其，那么第35瓶对应的二进制为 0100011，从左到右，第2位、第6位、第7位数为1，那么我们让第2、6、7只老鼠去喝掉它，如果三只老鼠都死掉了，那么这一杯药水就是毒药，如果没有死或者没有死完，那么就不是毒药，因为这几只老鼠还可能要去喝别的药水，我们无法判断。

讲解结束，开始实践

实践推演

我们使用 Excel 来进行统计，就是列表。使用Python的二进制算法，得到1-100的所有二进制数，并导入 Excel。为七只老鼠编号，使它们喝与之对应的药水。

我们假定第 84 号药水有毒，接下来进行推演

我们可以看到，当一组中，所有老鼠全部死亡时，才能判断这组为毒药，也就是第85瓶。

换位思考

当我写表格的时候，我发现如果不使用数学思维，我们把它看成生物遗传，当同时满足这几个基因均为显性基因时，才能够使得表现型为显性，但是我们要明白二进制解法是一个关键的点，如果没有二进制，我们很难完成。