leetcode中poor pigs解法分析

说来惭愧, 保研之后浪了一个月, 整个10月份基本都在玩, 就背了点单词, 11月份初回到学校, 开始了继续学习的过程, 基本11月主要做的都是刷题以及看看计算机网络的问题, 不得不说经历了春招, 我能非常明显的感觉到了算法的重要性,以及通过实习经历,知道了网络在开发中的重要地位,基本任何一个项目都难免涉及到与网络打交道,所以以后打算将重点放在这两个方面.

1. 本文想讲的问题是leetcode上的一道题目,序号是458, 名字为poor pigs, 题目如下图所示:

   
   image.png
   

   题目的意思翻译过来也很简单, 就是先给我们一个引子, 有1000个装满液体的桶,这里有一桶里面盛满了毒药,其余的都是水,这些液体以及桶看上去都是一样的. 一头猪猪如果喝了毒药, 那么它就会在15分钟内死亡.现在让我们求,给定一个小时用最少的猪猪的数量来找出那桶毒药. 下面是题目的扩展,也就是假设有b个桶,猪猪喝了毒药会在m分钟内死亡, 给定的最大寻找毒药桶时间为t分钟, 求最小的猪猪的数量.

2. 个人的一开始思路是很简单的, 假设一开始有n头猪, 那么利用类似于二分法的思路, 我将b个桶分为n份, 这样在m分钟就能找到哪一份会使猪猪死亡,接下来的思路也是相似的, 不过值得注意的是猪猪的数量是减少了一个的, 因此,每次分的份数都是要减1的, 最终的结果肯定最后一次测试的时候, 猪猪的数量大于桶的数量, 这样才能做到一次测试就完成.
   思路很直接, 不过比较可惜的是, 答案并没有这么直接就能得到, 下面我们来介绍, 正确答案的思路是怎么样的.

3. 我们先从简单的情况并换个角度开始考虑, 假设我们现在有两头猪, 毒药的药性是15分钟,我们有60分钟的寻找毒药时间, 最多能从25个桶中找出毒药, 看到数字是25我还是很惊讶的, 具体的解释如下:我们将25个桶排列成如下的形式:
   

   image.png
   核心来了,我们用一个猪猪来寻找毒药桶所在的列行, 就比如先让猪猪喝1,2,3,4,5,等待15分钟, 如果没死亡, 就继续喝下一行的桶,也就是6,7,8,9,10,再等待15分钟. 这个时候, 第二天猪的作用也就很明朗了, 我们用这头猪来寻找毒药桶所在 的列, 值得稍微提一下的是,两头猪是同时开始喝的,也就是说第一头猪喝1,2,3,4,5的时候, 第二头猪喝的是1,6,11,16,21,接下来的过程也就是不断的寻找会导致猪猪死亡的桶, 这个问题便迎刃而解了.

4. 接下来, 让我们顺着这个思路继续, 如果其他条件不变, 而猪的数量变为3呢, 那么我们最多能从多少个桶中找出毒药? 如果我们彻底理解了上面的解法, 那么这个问题也是不难的, 最大的桶的数量应该是5*5*5=125, 也就是说猪猪的数量实际上决定的是我们矩阵所在空间的维度, 通俗点来说,也就是说猪的数量决定了幂级数, 如前面所示, 当猪猪的数量是2的时候, 答案是5的2次方, 而当猪猪的数量是3的时候, 答案是5的3次方, 以此类推.

5. 现在的问题就变成了这个5是怎么来的呢, 实际上也很简单, 5 = 60/15 + 1, 稍微有点迷惑的地方就是为什么要加1呢, 这个也不难解释, 在3中的例子里, 如果毒药桶是在最后一行或者最后一列中, 假设毒药桶编号是10, 那么在第二次的测试中, 测试行的猪猪就会死亡, 这个时候我们可以确定毒药桶所在的行是第二行, 同时我们已经花费了30分钟的时候, 也就是还有30分钟测试时间, 也就是用一头猪有两次测试机会, 找出3个桶中哪一个是毒药桶, 我相信大家肯定能看出来, 最后一个是用排除法选出来的, 如果6,7,8,9,10中肯定有毒药, 但是6,7,8,9都不是毒药, 那么10必定为毒药, 也就说这个+1是来源于排除法的.

6. 到这里, 这个问题就解决的差不多了, 虽然单纯从刷题的角度来看这道题目是没有意义的, 因为这个完全是一道数学的题目, 但是我倒觉得数学作为基础学科, 是始终与计算机这种高新技术密不可分的, 因此, 在刷题过程中偶尔遇到这种数学题也未尝不是一种乐趣.