[leetcode][数学]可怜的小猪

原题链接https://leetcode-cn.com/problems/poor-pigs/

题目描述:

有 1000 只水桶,其中有且只有一桶装的含有毒药,其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药,它会在 15 分钟内死去。

问题来了,如果需要你在一小时内,弄清楚哪只水桶含有毒药,你最少需要多少只猪?

解题思路:

这个题我一开始觉得是个进制问题 实际上算是一个高深的信息论问题 牵扯到信息熵等知识 以及此类问题答案的上限
关于进一步的解答 请移步:https://www.zhihu.com/question/60227816/answer/175455729?utm_source=qq&utm_medium=social&utm_oi=694669088630267904
最初在知乎上看到的 看了高赞回答之后 觉得解题思路十分有趣 于是整理了一下
答案是5头 首先将1000桶按照5进制进行编码 5进制最多可以表示的桶的数量为(上限5位):5*5*5*5*5=3125
所以足以表示出1000桶水 之后按照正常思路在0 15 30 45时间分别喂给5头猪多瓶药水
具体方法如下:
将5头猪分别对应5位 之后每个时间点分别喂下0 1 2 3的水
就是在0时刻 第一头猪喂下所有最后一位是0的药水 第二头猪喂下所有倒数第二位是0的药水 以此类推
记住每头猪对应着一位 对应头猪死了能够说明该位的数字(5进制下是几)
表面上是测了0 1 2 3 实际上如果在60分钟的时候 还有猪没有死去 说明该位的数字是4 实际上一共测了5个次(这个5次是60/15=4+1得到的 和5进制没什么关系)
关于为什么是5进制 因为一个小时之后猪有五种状态分别是

  • 15分钟死了
  • 30分钟死了
  • 45分钟死了
  • 60分钟死了
  • 60分钟或者

关于x头猪能测多少桶水

2头猪能够测5桶水 那么 2 只小猪可以验证的范围最多到多少呢?我们把每只小猪携带的信息量看成是 base进制数,2只小猪的信息量就是pow(base, 2) = pow(5, 2) = 25 所以当 5 ≤ buckets ≤ 25时,anwser = 2
那么可以得到公式关系:pow(base, ans) ≥ buckets,取对数后即为:ans ≥ log(buckets) / log(base),因为 ans 为整数,所以
ans = ceil(log(buckets) / log(base))
实际上这个式子远没有这么容易得到 但是进一步讲涉及的知识我还理解不了

这里贴一个答主举得例子方便理解

在这里补充一个例子帮助大家思考这个问题:因为我们只在0,15,30,45分钟喂水,所以我们将这几个时间点记成第一二三四轮。5头猪称为1号猪2号猪3号猪4号猪5号猪。把1-1000号水按照5进制编号。

第一轮:喂1号猪5进制下末位数是0的水,喂2号猪5进制下倒数第二位数是0的水,喂3号猪5进制下倒数第三位数是0的水,喂4号猪5进制下倒数第四位数是0的水,喂5号猪5进制下倒数第五位数是0的水。

第二轮:开始前发现3号猪和5号猪死了。所以有毒的水的编号是0_0__. 喂1号猪5进制下末位数是1的水,喂2号猪5进制下倒数第二位数是1的水,喂4号猪5进制下倒数第四位数是1的水。

第三轮:开始前发现2号猪死了。所以有毒的水编号是0_01_. 喂1号猪5进制下末位数是2的水,喂4号猪5进制下倒数第二位数是2的水。

第四轮:开始前发现1号和4号还活着。喂1号猪5进制下末位数是3的水,喂4号猪5进制下倒数第四位数是3的水。

到60分钟的时候,发现1号死了,4号还活着。所以有毒的水的编号是04013。这个数在10进制下是508,所以是508号桶水有毒。

作者:Sun Ao
链接:https://www.zhihu.com/question/60227816/answer/175455729

进阶问题

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

思路

我们前面得出了 ans = ceil(log(buckets) / log(base))
将题目中的数值带入可以得到 x=ceil(log(n)/log(base))
base怎么求得 显然
base=p/m+1

代码

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int base=minutesToTest/minutesToDie+1;
        int ans=ceil(log(buckets) / log(base));
        return ans;
    }
};

问题后续的讨论

1000桶里面1桶毒药是5头猪 那么两桶毒药至少需要多少头猪?
根据信息论可以算出需要9头 但是具体的方法嘛 就复杂的多了
有兴趣的可以移步https://www.zhihu.com/question/60461214

发表评论

电子邮件地址不会被公开。 必填项已用*标注