给定n个金币，这是重了一些，发现重的硬币的数目？ [英] Given n coins, some of which are heavier, find the number of heavy coins?

问题描述

给定n个硬币，其中有一些是较重的，算法查找使用Ø重的硬币数量（日志^ 2 n）的称量。注意，所有重硬币具有相同的重量和所有轻的共享相同重量太

Given n coins, some of which are heavier, algorithm for finding the number of heavy coins using O(log^2 n) weighings. Note that all heavy coins have the same weight and all the light ones share the same weight too.

正在给使用它你可以比较硬币的两个不相交的子集的权重的平衡。注意，平衡仅指示哪个子集较重，或他们是否具有相等的权重，而不是绝对重量

You are given a balance using which you can compare the weights of two disjoint subsets of coins. Note that the balance only indicates which subset is heavier, or whether they have equal weights, and not the absolute weights.

推荐答案

我是不会放弃的全部答案，但我会帮你打破它。

I won't give away the whole answer, but I'll help you break it down.

1. 找到一个 O（日志（N））算法来找到一个沉重的硬币。
2. 找到一个 O（日志（N））算法拆分一组分成两组与同等数量的重型和轻型数最多两个剩菜（何时有甚至没有量的每种的）。
3. 联合算法＃1和＃2。

1. Find a O(log(n)) algorithm to find a single heavy coin.
2. Find a O(log(n)) algorithm to split a set into two sets with equal number of heavy and light counts plus up to two leftovers (for when there are not even amounts of each).
3. Combine algorithms #1 and #2.

提示：

• 在算法＃1独立的算法＃2。
• O（日志（N））暗示的二进制搜索
• 如何可能你结束了 O（日志^ 2（N））有两个 O（日志（N））算法？

• Algorithm #1 is independent of algorithm #2.
• O(log(n)) hints at binary search
• How might you end up with O(log^2(n)) with two O(log(n)) algorithms?

这篇关于给定n个金币，这是重了一些，发现重的硬币的数目？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！