前几天翻到一个很棒的技术博客,无意中扫到一道关于老鼠测试药水是否有毒类型的题目,没想到又能学到一个叫汉明码的东西。

导言

这是一道淘宝校园招聘会笔试题中的单选题(2011.9.21)。

我们有很多瓶无色的液体,其中有一瓶是毒药,其它都是蒸馏水,实验的小白鼠喝了以后会在5分钟后死亡,而喝到蒸馏水的小白鼠则一切正常。
现在有5只小白鼠,请问一下,我们用这五只小白鼠,5分钟的时间,能够检测多少瓶液体的成分?
A. 5瓶
B. 6瓶
C. 31瓶
D. 32瓶

看完的第一眼我就懵逼了,A和B肯定是错的,因为5瓶是最少可以检测出来的量,6瓶是最常规的想法得出来的。

然而,再按照6瓶的思路思考,能够检测的数量肯定大于6,但是不知道怎么检测出来的,于是求助了万能的度娘。

汉明码

汉明码,又称海明码,英文 Hamming Code 。

与其他的错误校验码类似,汉明码也利用了奇偶校验位的概念,通过在数据位后面增加一些比特,可以验证数据的有效性。
利用一个以上的校验位,汉明码不仅可以验证数据是否有效,还能在数据出错的情况下指明错误位置。

汉明码的作用,摘自百度百科。

Hamming Code 的伟大之处就在于他不仅可以校验有效性,还可以指出错误的位置。

在此,只浅谈 Hamming Code 的原理,并以该题目为例子讲通这个思想,若要深究可以继续度娘。

假设有一串数据的 Hamming Code 为 00100 ,那么这串数据是有误的,而且错误位是第4个数字。

相对的, 00000 代表这串数据是没有任何问题的。

好,我们只需要理解校验码怎么解读就可以解决这道题了。

题解

我们把每位老鼠按照顺序喝不同的药,每一只老鼠,活则为0,死则为1

以三只老鼠能测多少药为例,可以检测 2^3-1=7 瓶药。

三位老鼠可以得到 3 位二进制的编码,也就是可以代表 1 ~ 7 瓶药。

C B A
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

然后按照我们上面安排好的顺序,老鼠 A 的位数上是 1 则喝下该编码的液体,老鼠 B 和 C 也同理。

我们可以得到下面的表格:

老鼠 A 喝 1 3 5 7
老鼠 B 喝 2 3 6 7
老鼠 C 喝 4 5 6 7

假设没有老鼠没死,那么老鼠组成的校验码为 000 ,说明没有遇到毒药。

假设老鼠1死了,那么老鼠组成的校验码为 001 ,那么说明检测到了毒药,毒药是第1瓶。

假设老鼠1、3死了,那么老鼠组成的校验码为 101 ,那么说明检测到了毒药,毒药是第5瓶。

综上,3只老鼠检测了7瓶药。

以五只老鼠(原题)为例,可以检测 2^5-1=31 瓶药。

如上三只老鼠同理,用 5 位二进制数编码 31 瓶药,让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子,让第二只老鼠喝掉所有二进制数右起第二位是 1 的瓶子,以此类推。

老鼠 1 喝 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
老鼠 2 喝 2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31
老鼠 3 喝 4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31
老鼠 4 喝 8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31
老鼠 5 喝 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

与上面一例同理, 00000 则代表没有老鼠遇到毒药, 00001 则代表第1瓶是毒药,依此类推。

所以该题的答案选C,2^5-1=31

用代码计算出每只老鼠喝的药的顺序,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# [email protected]
# create=20160323

if __name__ == '__main__':
mouse_count = int(input("[*] 输入老鼠个数为: "))
mouse_max = pow(2, mouse_count)
for mouse_id in range(1, mouse_count + 1):
# 每只老鼠的编号
print("[+] 老鼠 %d 喝:" % mouse_id)
for at_apnot in range(1, mouse_max):
if at_apnot & (0x1 << (mouse_id - 1)):
print(at_apnot)

扩展

老鼠与毒药类型的题目,属于编码类问题,把握这类题的思路,类似的问题都好解决。

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

按照我们原来的思路,我们可以得知 10 只老鼠最多可以检测 1023 瓶液体。

2^10 - 1 = 1023 > 1000 > 2^9 - 1 = 511

那么我们只需,把 1000 个瓶子按照 1 ~ 1000 编号,让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子,让第二只老鼠喝掉所有二进制数右起第二位是 1 的瓶子,以此类推。

比如说,第一只老鼠喝 0000 0000 01 (#1) ,第二只老鼠喝 0000 0000 10 (#2),以此类推。

再扩展一下:

如果你有两个星期的时间(换句话说你可以做两轮实验),为了从 1000 个瓶子中找出毒药,你最少需要几只老鼠?

注意,在第一轮实验中死掉的老鼠,就无法继续参与第二次实验了。

答案是 7 只老鼠就够了,而事实上,7 只老鼠足以从 3^7 - 1 = 2186 个瓶子中找出毒药来。

首先,把所有瓶子从 1 到 2186 编号,然后全部转换为 7 位三进制数。

现在,让第一只老鼠喝掉所有三进制数右起第一位是 2 的瓶子,让第二只老鼠喝掉所有三进制数右起第二位是 2 的瓶子,以此类推。

7 6 5 4 3 2 1
0 0 0 0 0 0 1 - 1
0 0 0 0 0 0 2 - 2
0 0 0 0 0 1 0 - 3
0 0 0 0 0 1 1 - 4
0 0 0 0 0 1 2 - 5
0 0 0 0 0 2 0 - 6

一星期之后,如果第一只老鼠死了,就知道毒药瓶子的三进制编号中,右起第一位是 2

如果第二只老鼠没死,就知道毒药瓶子的三进制编号中,右起第二位不是 2,只可能是 0 或者 1 ,也就是说,每只死掉的老鼠都用自己的生命确定出了,三进制编号中自己负责的那一位是 2 ;但每只活着的老鼠都只能确定,它所负责的那一位不是 2 。

于是,问题就归约到了只剩一个星期时的情况。

假设老鼠 #1 #4 #7 死了,那么我们可以得到不完整的三进制编码:2 ? ? 2 ? ? 2

x 6 5 x 3 2 x
0 0 0 0 0 0 1 - 1
0 0 0 0 0 0 2 - 2
0 0 0 0 0 1 0 - 3
0 0 0 0 0 1 1 - 4
0 0 0 0 0 1 2 - 5
0 0 0 0 0 2 0 - 6

在第二轮实验里,让每只活着的老鼠继续自己未完成的任务,喝掉它负责的那一位是 1 的所有瓶子。

以此为例就是让,老鼠 #2 #3 #5 #6 喝那一位是 1 的所有瓶子。

再过一星期,毒药瓶子的三进制编号便能全部揭晓了。

我们假设老鼠 #5 #2 死了,那么我们可以得到完整的三进制编号 2 0 1 2 1 0 2 (1604),即十进制的 1604 也就是说瓶子 #1604 是毒药。

思路大概是,我们有多一轮(两轮)测试机会,那么我们可以多一位进制数。每一轮测试机会我们可以降低这个位数数字的不确定性,在这个案例中,两轮测试结束我们就可以得到精确度三进制编码,从而利用三进制转换成十进制得到毒药的编号。

类似地,我们可以证明, n 只小白鼠 t 周的时间可以从 (t+1)^n 个瓶子中检验出毒药来。

引用

趣题:老鼠与毒药问题的推广

淘宝2012笔试(研发类)