leetcode-可怜的小猪解法

曾经终败给现在 2023-06-11 05:19 3阅读 0赞

# [418、可怜的小猪][418] #

> 有 1000 只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在 15 分钟内死去。
> 
> 问题来了，如果需要你在一小时内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？

回答这个问题，并为下列的进阶问题编写一个通用算法。

**进阶**:

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

**提示**：

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

**题解：**

> 用信息论的概念来求解

*  一共有n个桶，要知道哪个桶有有毒药，至少需要\*math.log2(n)\*的信息量（对数的底数取多少不影响信息量的计算）
 *  每一只猪可以测试的次数是t=math.floor(minutesToTest/minutesToDie)。每只猪有t+1种状态，在第i次死亡（i:\[1,2,…，t\],或者存活，带信息量math.log2(t+1)
 *  答案就是math.ceil\[math.log2(n)/math.log2(t+1)\]

**代码：**

import math
    
    class Solution(object):
        def poorPigs(self, buckets, minutesToDie, minutesToTest):
            """ :type buckets: int 桶的数量 :type minutesToDie: int 几分钟死亡 :type minutesToTest: int 测试多长时间 :rtype: int 总共需要多少小猪 """
    
            number = math.floor(minutesToTest / minutesToDie)
            return math.ceil(math.log2(buckets)/math.log2(number+1))

[418]: https://leetcode-cn.com/problems/poor-pigs/