原题链接：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
Comments | NOTHING