优化查找中毒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 层树。

将每只老鼠分配到除根之外的树层。每只老鼠只会吃其所在级别左侧树枝上的饼干。第二天，遍历树，对于每只死去的老鼠，沿着左分支走，对于每只活着的老鼠，沿着右分支走。得到的饼干应该是有毒的。