算法题-关于老鼠与毒药的问题解析

边改BUG边写BUG

问题描述:
有100个一模一样的瓶子，其中99瓶中装的是普通的水，一瓶是毒药，水和毒药只能通过老鼠来分辨，喝下毒药的老鼠会在一个星期后死亡（刚好一个星期）。现在你有一个星期时间，请问至少需要多少只老鼠才能确定出哪个瓶子装的是毒药？


我本来想的是用坐标的方式来确定哪一瓶是毒药:
1、摆成2x50,4x25,5x20,10x10的方阵
2、每行都放一只老鼠，然后让老鼠把这行水都喝一口
3、每列放一只老鼠，然后让老鼠把这列水都喝一口
4、一周后测试每一行和测试每一列的老鼠中都会有一只死亡，通过死亡的老鼠就可以判断毒药的坐标啦
5、需要的老鼠数量=方阵的长度+宽度
   所以10x10的方阵最合适，需要老鼠20只
6、后来又想了想，为什么不建一个三维的坐标系呢，经计算4x5x5的坐标系最合适，所需老鼠=4+5+5=14只


最后看了其他解题方式之后,了解到这是一个二级制问题,用七只老鼠即可解决
这个解体思路，非常巧妙



我们知道2的10次放等于1024，那么通过把瓶子编成二进制，同时把老鼠变成二进制的位值就可以分辨到底哪瓶水是毒药

1.利用二进制来做，最少的老鼠数量就是计算2的多少次方大于等于瓶子数量，例如本题为7(2的7次方为128,大于100)。对100瓶进行二进制编码，这样可以排列出1xxxxxx，x1xxxxxx，...，xxxxxx1这样的七组序列。如第一瓶药水编码为0000001，第五瓶药水编码为0000101，第一百瓶药水的编码是1100100.

2.把老鼠分辨编成1-10号，分别对应二进制的第1位，第2位.....第10位

3.根据每瓶水的二进制代码给老鼠喝水，该位值为1就给该位值的老鼠喝，为0就不喝，比如，第一瓶药水编号为0000000001，就只给1号老鼠喝，第84瓶，编号是1010100 ,就给3号，5号，7号老鼠喝

4.1星期后，看哪些老鼠死了，然后死的老鼠位为1，没死的老鼠位为0，组成二进制数，该数对应的瓶子编号就是有毒的编号

---

解决完这题之后让我想起曾经学过的海明码,海明码在校验时有异曲同工之妙

海明码:是一种编码方式,他的特点就是能够发现双比特位错误,和纠正单比特错误
动一发而牵全身
举个例子,假如说我们现在要发送四位数据,我们现在就会在他身上插入一些冗余数据,这也被成为冗余码,或者校验码,这些校验码不仅可以校验自身也可以校验其他特定数据位
假设数据在接收的时候,发生了差错,我们就可以通过校验码检测出来,哪一位发生了错误

海明码工作流程
1.确定校验码位数r
2.确定校验码和数据的位置
3.求出校验码的值
4.检错并纠错

一、  确定校验码位数r

这里k为我们需要传递的信息,r就是为了校验差错而插入的冗余信息,也就是校验信息
假设我们要发送的数据: D=101101
数据的位数是k=6
满足不等式的最小r 为4
那么就是说D=101101的海明码应该有6+4=10位
其中原数据6位,校验码4位

二\确定校验码和数据的位置
假设这4位校验码分别为j1,j2,j3,j4  数据从左到右为s1,s2...s6.
首先我们来确定校验码应该放在什么位置
校验码是放在2的几次方的位置,也就是说,校验码只能放在2o,21,22,23,这些位置

剩下的空位,以此将 原数据填位即可
即可得出一下内容


三\接下来我们来求校验码的值
我们在上图的基础上添加二进制信息
我们知道校验码可以校验其他位置上的信息,那是怎么校验的呢,对于j1而言,我们可以看到他的数据位对应的二进制中1在最后一位,也就是第一位,那我们,就去看,那些数据的第一位也是1,那我们就可以确认那些数据是被j1所校验的位置

由此我们知道j1所校验的位置是s1,s2,s4,s5
那怎么求出校验位的值呢
我们令所有要校验的位 亦或 (⊕) 为0,带上j1自身  (同为0 ,异为1)
也就是j1 ⊕ s1 ⊕ s2 ⊕ s4 ⊕ s5  => 0
J1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0  => 0
J1 ⊕     1  ⊕ 1 ⊕ 0  => 0
J1 ⊕          0 ⊕ 0  => 0
J1 ⊕            ⊕ 0  => 0
由此可以得出j1为0

同理j2,要校验的位置是: s1,s3,s4,s6
J2 ⊕ s1⊕ s3⊕ s4 ⊕ s6=> 0
J2 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1  => 0
J2 ⊕     0 ⊕ 1 ⊕ 1  => 0
J2 ⊕          1 ⊕ 1  => 0
J2 ⊕            ⊕ 0  => 0
所以j2为0
以此类推可以得出下图


四\检错并纠错
所以101101的海明码就是0010011101.
我们假设第五位出错,因此我们接收到的数据位:0010111101

那我们怎么通过海明码来纠错呢
我们令所有要校验的位亦或运算
J1 ⊕ s1 ⊕ s2 ⊕ s4 ⊕ s5  
=> 0 ⊕ 1 ⊕ 1 ⊕  1 ⊕ 0 = 1

J2 ⊕ s1 ⊕ s3 ⊕ s4 ⊕ s6
=> 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0

J3 ⊕ s2 ⊕ s3 ⊕ s4
=>0 ⊕ 1 ⊕ 1 ⊕ 1 = 1

J4 ⊕ s5  ⊕ s6
=>1 ⊕ 0 ⊕ 1 = 0

二进制序列为0101 ,对应的十进制就是5 ,这样我们就找到了出错的位置 ,也就是第五位

swellfish

c03xp 发表于 2021-7-14 10:01
这好像跟天数没关系，你给1年它也是7只老鼠

给一年时间，就是52个星期，我用两只老鼠，第一只从第一瓶开始喝，每星期喝一瓶。第二只从第51瓶开始喝，也是每星期一瓶，看他们两个哪个喝完那一瓶挂了，那我是不是用两只就行了。

spring819

一脸懵逼的进来 ，又一脸懵逼的出去，，
读书时，老师教的进制转换，都忘记了，
还好，现在网上有这些转换的小程序
不过能想到这个思路也是极好的

xtx

涨知识了。学习一下。

侃遍天下无二人

确实7只就够了，因为7个二进制位可以表示128种状态
不过我比较懒，我就拿100只或者1000只老鼠来做实验

中国卢沟桥

这个太有深度了，需要收藏下来，深度学习一下。

hunterking

一脸懵逼

Mr.[先知]

经典算法题

飘零星夜

楼主,讲一下CRC如何,  汉明码的 竞争对手啊

zc199068

虽然你说的很有道理，但是。。。为啥鸽子那么大

三滑稽甲苯

很好的拓展思路的例题

MengSec

大佬牛逼，思路可以