algorithm - 找到两个不同的硬币

Question

这是问题所在：

你有 n 个硬币，其中 n = 2^k 的整数 k 使得 n - 2 个硬币的重量相同，两个硬币的重量比其他硬币重。两个较重的硬币可能重量相同，也可能重量不同。您有一个天平秤：您可以一次在秤的每一侧放置任意数量的硬币，它会告诉您两侧的重量是否相同，或者如果重量不同，哪一侧更轻。概述使用 O(log n) 称重找到两个较重硬币的算法。

如果只有一枚硬币与其他硬币不同，我知道答案。我还发现了类似的问题，即已知不同的硬币更重。

给定 n 个硬币，其中一些更重，找到重的硬币的数量？

任何帮助。

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)。