返回题库

找出真金硬币

Pure Gold

专题
Strategy / 策略
难度
L6

题目详情

有 NN 枚外观相同的硬币（可假设 N=2kN=2^k）。其中部分是真金（更重），其余是镀金铝（更轻）。

你有一架天平（两盘比较）。真金硬币重量相同，假币重量也相同。

问：最少需要多少次称重，才能把真金与假币完全分开？

提示：分治。

You are given N coins which look identical (assume N = 2^k). But actually some of them are pure gold coins (hence are heavy) and the rest are aluminum coins with thin gold plating (light). You are given one beam balance with two pans. What is the number of weighing required to separate the gold from fake coins? (all gold coins have equal weights & all fake coins too have the same weight)

Hint

Divide and conquer

解析

复杂度为 O((log⁡N)2)O((\log N)^2)。

当 N=2kN=2^k 时，可做到精确约为

k(k+1)2\frac{k(k+1)}{2}

次称重（其中 k=log⁡2Nk=\log_2 N）。

思路：递归把集合一分为二，并通过若干次称重把“较重硬币数量”在两半中尽量均分，再分别递归。

Original Explanation

Solution

It takes about (log N)^2 operations: Divide the set of 2^k with d heavy coins into two sets, each with 2^(k-1) coins with floor(d/2) heavy coins. If we can do this, we can determine the number of heavy coins in O(log n)^2 operations.

Dividing the set can be done in O(log n). (*Later)

So, T(n) = T(n/2) + O(log n) T(n) = O(log^2 n). To be exact, this is k*(k+1)/2 . where k = log N

(*Sub-Algorithm) Divide the set into two sets A and B of equal number of coins. Let A greater than B and to make both side of equal weight, I need to shift few coins from A to B and equal number of coins from B to A. So divide A into A1 and A2, and B into B1 and B2. Move A2 from A into B and B1 from B into A now if (A1,B1) is greater than (B2,A2) then I have not moved enough coins from A into B so as to make B part heavy enough hence you divide A1 into A11,A12 and move A12 in B side similarly u move B21 into A side on the other hand if (A1,B1) is less than (A2,B2) I have more than enough coins from A into B hence move B12 back into B and A21 back into A now measure again. Do it so on...

Note that we are doing this in O(log n) as each time the number of coins we are moving is reduced by half. So, In O(log n), we are done.

To prove that solution always exists, we do it by induction: difference in the number of heavy coin after kth iteration cannot be more than 2^(n-1-k) So, after n-1th iteration, it can be more that 1 coin. Hence, done. :)