algorithm - 优化发现中毒 cookie 的天数

Question

我的一个朋友在面试时被问到这个问题，当时无法解决。以为我会分享同样的。

有一千个巧克力曲奇，其中一个中毒了。您每天可以接触 10 只实验室老鼠。每只老鼠可以啃任意数量的饼干，每个饼干可以被任意数量的老鼠啃。老鼠咬了一块有毒的饼干后，需要一天的时间才能看到老鼠中毒后的后果。

优化天数。我能够想出一个算法在 2 天内找到中毒的 cookie，尽管我相信有一种方法可以在 1 天内做到这一点

Answer 1

这是三天内的“简单”解决方案：

• 首先，让每只老鼠啃 100 块饼干。
• 一天后，让每只老鼠啃掉 10 块死老鼠吃的饼干。
• 两天后，让每只老鼠吃掉第二只死老鼠吃的饼干。
• 三天后，你就会知道哪个饼干中毒了。

现在对于一天内的“硬”解决方案：

• 以二进制对所有 cookie 进行编号。
• 每只老鼠都将啃咬那些二进制表示在老鼠索引处有一个设置位的cookie。因此，例如，老鼠 1 将蚕食所有奇数 cookie。
• 换句话说，饼干 37 会被老鼠 1、3 和 6 蚕食。所以如果这三只老鼠在第二天死了，你就知道饼干 37 是中毒的老鼠。

Answer 2

我想我明白了。

想象一棵以 1024 个 cookie 为根的二叉树（这个数字更清晰，但这适用于任何小于 1024 的数字）。将 1024 个 cookie 分成两组，每组 512 个，每组都是根的孩子。然后将这些 512 组中的每一个分成 256 组，并让它们成为每个组的孩子，依此类推。您应该最终得到 11 个级别的树。

将每只老鼠分配到除根之外的树的一个级别。每只老鼠只会吃掉他们关卡左边树枝上的饼干。第二天，遍历树，对于每只死去的老鼠，跟随左分支，对于每只活着的老鼠，跟随右分支。生成的 cookie 应该是有毒的。