请你找出毒酒

来源:百度知道 编辑:UC知道 时间:2024/07/04 14:43:06
国王为10天后的生日宴会准备了1000桶酒,不幸的是,其中两桶被下了毒。为了确定两桶毒酒,有人提议用死刑犯试毒。毒的潜伏期为10天。问:至少需要多少个死刑犯才能确保找出毒酒?方案如何实行?

首先简单来说我们先假设只有10桶酒,其中有一桶被下了毒,那个需要多少个死刑犯呢?

为了能够充分利用这些死刑犯,每个人肯定需要尝试多桶酒,那么对于死刑犯来说,对于每一瓶酒喝与不喝有两个选择,我们分别记为0和1,那么对于每一个死刑犯来说,就会产生一个10位的二进制数,我们先假设全部不喝,并如下所示把它们横着排列起来:

酒 1 2 3 4 5 6 7 8 9 10
死刑犯1 0 0 0 0 0 x1 0 0 0 0
死刑犯2 0 0 0 0 0 x2 0 0 0 0
死刑犯3 0 0 0 0 0 x3 0 0 0 0
......
死刑犯n 0 0 0 0 0 xn 0 0 0 0

如上所示,如果我们竖起来看的话,每一列的二进制数据就决定了某一桶酒相对应有哪些死刑犯来喝
比如上图中(x1,x2,x3,...,xn)的意思就是说 对于6号桶酒来说,如果xn=0 则死刑犯n不用喝,如果xn=1 则死刑犯n需要喝
所以如果要用最少的死刑犯来找出毒酒的话,就需要10组不同的二进制数(相同没有意义)
那么如果需要10组不同的二进制数,最少需要几位呢?很显然需要4个,简单罗列如下:

酒 1 2 3 4 5 6 7 8 9 10
死刑犯1 0 0 0 0 0 0 0 1 1 1
死刑犯2 0 0 0 1 1 1 1 0 0 0
死刑犯3 0 1 1 0 0 1 1 0 0 1
死刑犯4 1 0 1 0 1 0 1 0 1 0

结果很显然,如果1号桶有毒,那么只有4号死刑犯死了,其他情况大家可以自己试试看
当然4位的二进制后面还有,所以4个死刑犯其实最多能找出出16桶酒中被下了毒的那1桶酒。

好了,现在10桶酒中有2桶被下了毒,那么怎么办呢?

答案很简单,10桶中1桶被下毒则有10中情况
而10桶中2桶被下毒则有10x9/