algorithm - 查找 0(log^2(n)) 中的所有重硬币

Question

假设给你 n 个硬币，其中一些很重，另一些很轻。所有重硬币的重量都相同，所有轻硬币也一样，重硬币的重量严格大于轻硬币的重量。已知至少有一枚硬币很轻。你得到一个天平，你可以用它来衡量一个硬币子集和另一个不相交的硬币子集。展示如何使用 O(log2 n) 称重来确定重硬币的数量。

Answer 1

我想这一定是对你有 8 个硬币并且其中一个很轻的问题的概括。因此，您可以执行一种二进制搜索，以便使用一对天平找到最轻的硬币。然而，奇怪的是你竟然要同时找到几个轻币。在这种情况下，这似乎与 log2 n 不成比例。

请参阅下面的示例以理解我的观点。在 8 个硬币的情况下，其中一个是轻的。您应该遵循三个步骤：

步骤 1) 将样品分成两部分，找到最轻的部分。=> 1 权重。[你得到了一个更轻的 4 个硬币的样品]

步骤 2) 划分上一个过程中最轻的部分并对这些部分进行加权以找到最轻的部分。=> + 1 个权重 [你有一个包含 2 个硬币的样本]

步骤 3) 现在你只有两个硬币。您只需对它们进行称重即可找到最轻的。

当然，对大小为 n 的样本的推广是微不足道的。

这与 log2 n 成比例的证明遵循二分搜索证明。

但是，如果轻硬币的数量不是 1，则不能只关注样本中最轻的部分。[免责声明：也许我错了，但很难说这将与 log2 n 缩放。例如，考虑轻硬币的数量与 n（硬币数量）成比例的情况]

实际上，这个问题最漂亮的解决方案是在两个权重中找到最轻的硬币：

步骤 1) 将样品分成 3 部分。第一部分有 3 个硬币，第二部分也有 3 个硬币，最后一部分只有 2 个。

步骤 2) 对第一部分和第二部分进行加权。有以下三种情况：

a) 第一部分较轻。

b) 第二部分更轻。

c) 第一部分和第二部分重量相同。

If (a or b) wight 其中两个。如果它们的重量相同，则另一个没有加重的重量更轻。另一方面，如果它们的重量不同，则其中一个是较轻的

if(c) 只需将两枚硬币称重即可找到较轻的一枚。

这也可以泛化，但泛化要复杂得多。