找到两个不同的硬币

 

这是问题：

你有n个硬币，其中n = 2 ^ k的整数k，这样n-2个硬币具有相同的重量，两个硬币的重量比其他硬币大。 两个较重的硬币可能具有相同的重量，或者它们的重量可能不同。 你有一个平衡秤：你可以同时在秤的两侧放置任意数量的硬币，它会告诉你双方重量是否相同，或者如果重量不一样，哪一侧更轻。 概述使用O（log n）称量来查找两个较重硬币的算法。

如果只有一枚硬币与其他硬币不同，我知道答案。 而且我也发现类似的问题，其中不同的硬币已知较重。

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

任何帮助。

假设你将硬币分成两堆2k-1硬币。

  • 如果两堆重量相同，那么你知道每堆必须包含一个较重的硬币，并且两个较重的硬币重量相同。 在每一堆上使用你的“一个更重的硬币解决方案”。
  • 如果两个桩的重量不相同，则将较轻的桩分成两个2k-2个硬币的桩。 这里的想法是，我们还不知道较重的一堆有两个重的硬币，或者每一堆都有一个（而较重的一堆有最重的硬币），我们将使用第二个称量来找出哪一个。
  • 如果这两个桩的重量不相同，那么第一次称量的两个硬币堆中的每一个都必须有一个重硬币（并且这两个重量不同）。 在每一堆上使用你的“一个更重的硬币解决方案”。
  • 如果这两堆重量相同，那么这两个重硬币必须处于较重的2k-1个硬币堆中。 在那堆上缓行。 （并且我们会弄清楚这两个重硬币是不是稍后称重）。

    • 现在，为了称量的数量的证明。

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

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

    链接地址: http://www.djcxy.com/p/70673.html

    上一篇: Finding the two different coins

    下一篇: Given n coins, some of which are heavier, find the number of heavy coins?