優化查找中毒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是毒死一個被蠶食。