数据结构+算法=程序
程序+设计模式=框架

0%

薛定谔的猪

问题

有1000个瓶子里面装满了水,其中1瓶里面被加入了毒药,但是滴入毒药的水在外观上看和普通水是一模一样的,也就是说这1000个瓶子是分不清哪瓶是装有毒药的,除非把装有毒药的水喝进肚子里。现在有一只可怜的猪可以用来实验,将其中一瓶水喂给这只猪喝,如果猪毒发身亡了,说明这瓶水有毒。猪并不需要喝完整瓶水,只需喝到一小口,毒性就会发作,如果水是有毒的话。

由于只有一只猪,所以我们只能一瓶一瓶的去试验,假如毒发的时间是1分钟,那么我们每喂完一瓶水,就等待一分钟,直到猪死亡。值得注意的是,我们只需喂完999瓶水即可,因为如果猪喝完前面的999瓶水还没有中毒的话,说明最后一瓶一定是有毒的,已经不需要再试验了,同时这只猪也是幸运的,它可以告别死亡的命运。所以,我们最多需要花费999分钟,或者说试验999次才能找到这瓶装有毒药的水。

那么问题来了,如果现在不是1只猪,而是有10只猪可以用来试验,那么你最少可以试验几次能找到这瓶有毒的水?

提示:我们可以将水混合到一起喂给猪喝,无论如何,只要猪喝到有毒的水就会死亡。

答案

如果你不熟悉二进制的话,可能会觉得不可思议。不过答案是只需1次,没错,我们只需让每只猪喝1次水,总共花费1分钟即可找到这瓶有毒的水。
猪喝完一瓶水后,它只会有2种状态,要么活着要么死亡,如果把这个状态看作二进制的0和1的话,那么10只猪可以表示$ 2^{10} $个状态,也就是1024个状态,已经超过1000个瓶子了,所以10只猪的前提下,我们只需试验1次即可。

原理

我们先将这1000瓶水,按0-999编号,前面说过10位二进制已经可以表示1024个状态了,所以完全能够表示这其中的所有编号。下面的表格是用二进制表示的所有编号:

每只猪占据了一个二进制位,比如编号1的猪(Pig1)就相当于二进制的最低位,Pig10为二进制的最高位。
参照这个表格,我们按列给猪喂水,只喂其中标记为1的瓶子。比如Pig1,我们就将瓶子1、瓶子3…瓶子999的水倒出来合到一个桶里,准备喂给猪1,简称桶1。

同理,我们将瓶子2、瓶子3…瓶子999的水再倒进另一个桶里准备喂给猪2,简称桶2。

以此类推,我们最终得到了10个桶,然后让10只猪分别喝这10桶水,并记住他们的编号。1分钟后,毒性发作,此时观察这10只猪的状态,根据状态我们就能确定唯一的毒瓶子。
比如只有猪3死亡了,而其他猪都活着,那么一定是4号瓶子是有毒的水,因为除了猪3喝过4号瓶子,其他猪都没有。

同理,如果只有猪4和猪5活着,其他猪都死了,那么一定是编号999的瓶子,因为死去的猪都要一个共通点,就是它们都喝过999号瓶子的水,而没死的猪一定没喝过999号瓶子。

如果够幸运,所有的猪都没有死,那么有毒的水一定在0号瓶子里面,因为只有这瓶水,所有的猪都没有喝过。
所以,根据猪的死亡情况,对照着表格的行,1代表死亡,0代表活着,我们一定能确定一种状态,而这个状态就对应着毒瓶子的编号。

进阶

通过前面的原理分析我们已经知道,在试验1次的情况下,每只猪有2种状态,生或者死,反过来说,如果有2只猪,那么可以最多测试几个瓶子?答案是$ 2^2 =4 $个瓶子,也就是状态数(2)的猪数量(2)次方。
假如我们给4个瓶子编号为0-3,2只猪分别表示A和B,用表格表示:

根据表格所示,我们让A喝瓶子1和瓶子3,让B喝瓶子2和瓶子3,一轮结束过后,2只猪的死亡状态可以确定唯一的毒瓶子编号。
为了深刻印象,同理,3只猪可以测试$ 2^3 =8 $个瓶子,我们用ABC代表3只猪,表格表示:

根据表格所示,每只猪对应的喝水情况:

  • A:瓶子1,瓶子3,瓶子5,瓶子7
  • B:瓶子2,瓶子3,瓶子6,瓶子7
  • C:瓶子4,瓶子5,瓶子6,瓶子7

当你按此分配,得到任意一种猪的生死状态后,即使不对照表格,也能通过排除法得到毒瓶子,有兴趣的朋友可以自行验算。

前面都是试验1轮的情况,如果是试验2轮呢?那么每只猪就应该会有3种状态,活着第1轮死掉第2轮死掉。以1只猪为例,那么最多可以测试$ 3^1=3 $个瓶子,第1轮喝瓶子1,如果活着进入第2轮喝瓶子2,2轮过后一定能测3个瓶子,由于是3种状态,所以就不能用二进制了,而应该用三进制,表格表示:

根据表格定义,假如猪最后的状态是状态2,也就是第二轮死掉,那么对应的毒瓶子编号就应该是2。

再来看2只猪试验2次的情况,同理,根据公式应该是$ 3^2 =9$,可以最多测9个瓶子,表格表示为:

其中,A始终占据数值低位,B始终占据数值高位,试验1中只填充数值为1的位,试验2中只填充数值为2的位,所以喝水策略为:

  • 第一轮:

    • A:瓶子1,瓶子4,瓶子7
    • B:瓶子3,瓶子4,瓶子5
  • 第二轮:

    • A:瓶子2,瓶子5,瓶子8
    • B:瓶子6,瓶子7,瓶子8

以此策略喂猪喝水,我们一定能通过猪最后的状态确定唯一的毒瓶子。

总结:
猪的状态数为试验轮数+1,根据猪的状态数和猪的个数,可以确定最多能测试的瓶子数量,这是一个通用解。

终极

来自力扣的困难题:458. 可怜的小猪
有 1000 只水桶,其中有且只有一桶装的含有毒药,其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药,它会在 15 分钟内死去。问题来了,如果需要你在一小时内,弄清楚哪只水桶含有毒药,你最少需要多少只猪?
回答这个问题,并为下列的进阶问题编写一个通用算法。

进阶:
假设有 n 只水桶,猪饮水中毒后会在 m 分钟内死亡,你需要多少猪(x)就能在 p 分钟内找出 “有毒” 水桶?这 n 只水桶里有且仅有一只有毒的桶。

提示:
可以允许小猪同时饮用任意数量的桶中的水,并且该过程不需要时间。
小猪喝完水后,必须有 m 分钟的冷却时间。在这段时间里,只允许观察,而不允许继续饮水。
任何给定的桶都可以无限次采样(无限数量的猪)。


解答:
如果你已经看懂了上面的所有分析,那么这题就变成了一道数学题。
猪饮水中毒后会在 m 分钟内死亡,代表一次实验的时间为m分钟,需要在p分钟内找出,则代表可以实验p/m次,也就是是说每只猪可以有p/m+1个状态,而猪的数量是x,瓶子的数量是n,根据公式则有$ (p/m+1)^x=n $,根据题目意思,pmn都是已知的,我们的目标就是求得满足该不等式$ (p/m+1)^x>=n $成立的x的最小整数值。
所以,对于这个通用函数,仅仅只需要一行代码:求以(p/m+1)为底,n的对数,并将结果向上取整。

1
2
def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
return math.ceil(math.log(buckets)/math.log(minutesToTest//minutesToDie+1))

换一种思路:
猪的状态数代表着n进制,这个n是已知的,这个问题也可以看作是n进制表示瓶子总数N需要的最小位数。比如对于十进制数字12,在十进制下表示需要2位,而二进制表示下是1100,则需要4位,现在我们只需将瓶子数转换成n进制表示,同时看会占据多少位即可。

1
2
3
4
5
6
7
def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
if buckets==1:
return 0
def baseN(N, b):
return "0" if N == 0 else (baseN(N // b, b).lstrip("0") + "0123456789abcdefghijklmnopqrstuvwxyz"[N % b])
base=minutesToTest//minutesToDie+1
return len(baseN(buckets-1,base))

我们并不是要通过程序去解一个方程题,重要的是,真正明白其中的原理。