优化查找中毒cookie的天数

Question

我的一位朋友被问及面试的这个问题，并且当时无法解决这个问题。以为我会分享一样的。

有一千块巧克力饼干，其中一块中毒。您每天可以使用10只实验室老鼠。每只大鼠可以在任何数量的小甜饼上轻咬，并且每个小甜饼可以被任意数量的大鼠啃咬。 大鼠在中毒的小甜饼上啃食后，需要一天的时间才能看到大鼠受到毒害后对大鼠的影响。

优化的天数。我能想出一个算法来找出中毒的cookie 2天，但我相信存在一种方法以1天

Answer 1

我想我得到了它这样做。

想象一个二叉树1024块饼干作为根（这个数字只是出来清洁，但是这会为任意数量小于1024的工作）。将1024个饼干分成两组512个，这些组中的每一组都是根的孩子。然后将每组512个分成256个组，然后让这些组成为其中每个组的子组，等等。你最终应该有11层树。

分配每只大鼠给除了根一树的水平。每只老鼠只吃他们关卡左侧的饼干。第二天，遍历树，并为每只老鼠死亡，按照左边的分支，对于每只老鼠，按照右边的分支。由此产生的cookie应该是中毒的。

Answer 2

这是三天内“易”解决方案：

• 首先，让每一个老鼠啃100个Cookie。
• 一天后，让每只老鼠吃掉死老鼠吃的饼干中的10块。
• 两天后，让每只老鼠吃掉第二只死老鼠吃的其中一块饼干。
• 三天后，您将知道哪个cookie中毒。

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

• 所有的二进制饼干数目。
• 每只大鼠都要咬那些饼干，其二进制表示在老鼠的索引处有一组位。因此，例如大鼠1将蚕食所有奇数曲奇。
• 换句话说，饼干37将老鼠1,3和6，所以，如果这些正好是三只死的第二天，你就知道该cookie 37是毒死一个被蚕食。