algorithm - 找到两个不同的硬币

Question

<分区>

Answer 1

假设您将硬币分成两堆，每堆 2^k-1 个硬币。

1. 如果两堆硬币的重量相同，那么您就知道每堆硬币一定包含其中一枚较重的硬币，并且两枚较重的硬币重量相同。在每堆上使用“一个较重的硬币解决方案”。
2. 如果两堆重量不一样，将较轻的那堆分成两堆，每堆有 2^k-2 个硬币。这里的想法是，我们还不知道是较重的那堆有两个重硬币，还是这两堆各有一个(较重的那堆有最重的硬币)，我们将使用第二次称重来找出是哪一个。
   • 如果这两堆硬币的重量不同，那么第一次称重的两堆硬币都必须各有一枚重硬币(并且两堆硬币的重量不同)。在每堆上使用“一个较重的硬币解决方案”。
   • 如果这两堆确实重量相同，那么两枚较重的硬币必须在较重的 2^k-1 硬币堆中.递归那堆。 (稍后我们会弄清楚这两枚重硬币的重量是否不同)。

---

现在，对于称重次数的证明。

假设我们从不使用“一枚重硬币解决方案”，这种设置在最坏的情况下将进行两次称重以将搜索空间减半。因此，这里的称重次数是2 log n。

请注意，我们最多使用两次“一个更重的硬币解决方案”。因此，松散的上限是上述两个步骤的 2 log n，加上“一个更重的硬币解决方案”的称重次数的 2 倍，得到 2 log n + 2 * O(log n)，仍然是 O(log n)。