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

 

给定n个硬币，其中一些较重，使用O（log ^ 2 n）称量来查找重硬币的数量的算法。 请注意，所有重磅硬币的重量都相同，所有重磅硬币的重量也相同。

给你一个平衡点，你可以用它来比较两个不相交的硬币子集的权重。 请注意，天平仅指示哪个子集较重，或者它们是否具有相同的权重，而不是绝对权重。

我不会放弃整个答案，但我会帮你分解它。

  • 找到一个O(log(n))算法来找到一个重的硬币。
  • 找到一个O(log(n))算法来将一个组合分成两组，其中重和轻计数等于最多两个剩余部分（当没有每个剩余量时）。
  • 结合算法＃1和＃2。

    • 提示：

  • 算法＃1独立于算法＃2。
  • O(log(n))提示二进制搜索
  • 如何用两个O(log(n))算法O(log^2(n)) ？
    • 链接地址: http://www.djcxy.com/p/70671.html

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

    下一篇: Graph Algorithm for Dismantling