网上有个很有名的问题是:10只老鼠,1000个瓶子,1个毒药问题?但如果是10瓶毒药呢?最少需要多少老鼠呢?

给1000个瓶分别标上如下标签(10位长度):
0000000001 (第1瓶)
0000000010 (第2瓶)
0000000011 (第3瓶)
......
1111101000 (第1000瓶)
从 编号最后1位是1的所有的瓶子里面取出1滴混在一起(比如从第一瓶,第三瓶,。。。里分别取出一滴混在一起)并标上记号为1。以此类推,从编号第一位是1 的所有的瓶子里面取出1滴混在一起并标上记号为10。现在得到有10个编号的混合液,小白鼠排排站,分别标上10,9,。。。1号,并分别给它们灌上对应 号码的混合液。24小时过去了,过来验尸吧:
从左到右,死了的小白鼠贴上标签1,没死的贴上0,最后得到一个序号,把这个序号换成10进制的数字,就是有毒的那瓶水的编号。

检 验一下:假如第一瓶有毒,按照0000000001 (第1瓶),说明第1号混合液有毒,因此小白鼠的生死符为0000000001(编号为1的小白鼠挂了),0000000001二进制标签转换成十进 制=1号瓶有毒;假如第三瓶有毒,0000000011 (第3瓶),第1号和第2号混合液有毒,因此小白鼠的生死符为00000011(编号为1,2的鼠兄弟挂了),0000000011二进制标签转换成十进 制=3号瓶有毒。


但是当有10瓶毒药后,例如仍然是1111101000号的结果,在只有一瓶毒药的情况下,确定是第1000瓶,但在有10瓶毒药的情况下,有太多情况0111101000+1111101000
1011101000+0111101000
0111101000+0111101000+11111101000+..........
............................
不知如何处理了,那究竟用什么方法才能用最少的老鼠检验呢?

推荐  (0) | 4人关注关注
5个答案
0 0

PalaeoBeaR喜欢编程的古生物工作者

2014-10-24 01:19

原题实际上是个很基础的,考位运算和二分搜索的算法题
你这样题目改了就没意义了

0 0

你这个问题有一个前件,那就是用最短时间找出来。
否则假如时间无限的话,我用一个老鼠就可以找出1000个瓶子中的1个毒药。

假如这种毒药的发作时间已知,可以每分钟给老鼠喂1滴来自不同瓶子的药水。老鼠死后,根据死亡时间反推瓶子的编号,再用1只老鼠验证,即可。

好吧,不偏离原题的本意,将其泛化为一个数学问题:
m个瓶子,其中n个有毒药,用x 张试纸来测试。要求:所用的测试策略必须把n个瓶子都找出来。每张试纸能且只能用1次,不管是否测出毒药都报废,并且不能把试纸劈开用。
求x = max(f(m, n))

max 是要求取最大值。比如1000个瓶子,10个有毒药,每次取1个瓶子、1张试纸来测试,运气最好的时候,用10张试纸正好测出。运气最差的时候,需要用999张。故此,这个策略的x = 999,是个很烂的办法。

现在,对于n = 1,答案是: x = ceil(log2(m)) 其中ceil 是进位法取整, 比如 ceil(2.0001) = 3。
对于n = 2,当
m = 3, x = 2
m = 4, x = 3
m = 5, x = 4
m = 6, x = 4
m = 7, x = 5
m = 8, x = 5
m = 9, x = 6
...

在这里,我的思维走入了误区,即怎样去组合瓶子。感谢楼下的@方弦 提供了正确的思路。
从信息量的角度,就可以正确计算x 。
x = max(f(m, n)) = ceil(log2(C(m, n)))

为免大家看括号晕掉,解释如下:
1. 计算m中取n 的组合,设为a
2. 计算log2(a),设为b
3. 计算ceil(b),即为答案x。

至于具体的策略,我想到了一个方案:
1. 找到小于m的最大的2的幂,设为p。用一张试纸,把m分割为p 和 m-p 两部分。
2. 对p的部分,执行每次将其分为相等两份的测试。
3. 对m-p的部分,重复1.

设m=16, n=8, 则信息量为16!/8!/(16-8)!= 12870,ceil(log2(12870)) = 14
假如样品的排序为最不理想的形式,即:XOXOXOXOXOXOXOXO (X有毒O无毒)

有个复杂的机制需要阐述
TO BE CONTINUE

可以证实,这种策略所用试纸数量不多于x,是一种理想的策略。
但是,我无法证明不存在其它更好的方案。

1 1

方弦科学松鼠会成员,信息学硕士生

2014-10-25 17:16
支持者: PalaeoBeaR

这种问题,首先第一个就是找下界。

1只老鼠,假设只实验一次,就给出1bit的信息。而1000个瓶子有10个有毒,大概的可能性数量是1000^10/10!,粗略估算是2^100上下,也就是说,至少需要大概100只老鼠才能达到目的。

然后具体的方案呢?可以参考最大化每次猜测的信息熵的策略,计算很麻烦,但是基本上都能解出来。

0 0

问了概率论老师,他提供了一个答案:
k个人一组进行分组,将每个人所抽的血取出一半混合在一起化验,如果结果是阴性,则对于这k个人来说,只需化验一次就够了;如果是阳性,再对k个人的血逐个化验,这时对k个人来说,则需要化验k+1
设每个人呈阳性概率为p,阴性概率为q=1-p,则k个人呈阴性概率为q^k,呈阳性概率为1-q^k,见下图

x
1
K+1
P
q^k
1-q^k

则E(x)=1*q^k+(k+1)(1-q^k)=k-q^k+1/k
将N个人分成N/k个组(假设N/K为整数),每组k个人
则总期望值E(X)=N/K*E(x)=N(1-q^k+1/k)
当N=1000时,p=0.01时,取K=11时
E(X)min=1000(1-0.99^11+1/11)=195.57
也就是只剩下原来的五分之一的工程量不到,且随p的减少而更加省却工程量了。

但是如上楼方弦的方式只需100次左右,想问一下还有更好的方式吗?总感觉还有什么别的方式

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区