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

Question

<分区>

Answer 1

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

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

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

第 2 步) 划分前面程序中最轻的部分，并对这些部分加权以找到最轻的部分。 => + 1 权重 [你得到了一个包含 2 个硬币的样本]

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

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

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

但是，如果光硬币的数量不是 1，则不能只关注样本中最亮的部分。 [免责声明:也许我错了，但很难说这会随着 log2 n 扩展。例如，考虑轻币的数量与 n(币的数量)成比例的情况]

其实这个问题最美的解法就是只用两种权重找到最轻的硬币:

第 1 步) 将样本分成 3 部分。第一部分是三个硬币，第二部分也是三个硬币，最后一部分只有两个。

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

a) 第一部分较轻。

b) 第二部分较轻。

c) 第一部分和第二部分具有相同的权重。

如果 (a 或 b) 有两个。如果它们的重量相同，则未称重的另一件重量较轻。另一方面，如果它们的重量不同，则其中一个较轻

if(c) 只是称重两枚硬币，找出较轻的那枚。

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