Featured image of post 利用 Python 解决“老鼠喝药水”问题

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

前言

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

题目

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

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

困难

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

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

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

二进制法

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

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

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

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

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

1
2
3
4
5
6
7
8
9
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 瓶。

换位思考

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

本博客已运行 days , h , m , s
常记溪亭日暮,沉醉不知归路~