algorithm - 分而治之算法在 O(logn) 中找到假币

Question

嗨!!我试图找到解决这个问题的信息和例子，但找不到。这是我的考试准备问题而不是作业。有人可以解释解决这个问题的步骤吗？而且，有没有像这样的相关示例的资源？欢呼!!

Answer 1

我将在 (log2(n) + 1) 步中给出解决方案。 +1就是找重还是轻。如果你知道那部分，它将采取 log2(n) 步。

分成两堆。比方说，A 和 B。将它们相互权衡，你会发现 A<B (阅读，A 堆的重量小于 B 堆的重量)。取一堆，比如 A，拆分并称量各个部分。如果它们的重量相等，您会得到 2 个事实:

• 假币在B
• 它比其他硬币重。

然后你继续堆 B。(你的 +1 称重。)

否则:

• 假币在A中
• 它比其他硬币轻。

现在，假设 A 包含假币。然后，将 A 的两堆命名为 A and B , 和, 重复。

PS:我用 3^n 个硬币解决了这个难题(几年前)。它也需要相同数量的步骤，因为它的复杂性是 (log3(n) (+1))。我将把它留作您要解决的下一个问题。

PPS:我将问题的第二部分留给您。申请Master's theorem你自己。
提示:与 binary search 相同.