Algorithm to find counterfeit coin amongst n coins

So this is the classic problem of finding a counterfeit coin among a set of coins using only a weighing balance. For completeness, here is one example of such a problem:

A well-known example has nine (or fewer) items, say coins (or balls), that are identical in weight save for one, which in this example is lighter than the others—a counterfeit (an oddball). The difference is only perceptible by weighing them on scale—but only the coins themselves can be weighed. Is it possible to isolate the counterfeit coin with only two weighings?

We are dealing with the case where only one of the coins is counterfeit and we know how it is so (ie we know it is heavier/lighter).

My question is, is there a general efficient algorithm to solve the generalized version of this problem for N coins with one counterfeit. I have been thinking about it and so far I have that if N is of the form 3^k , then you can find the counterfeit in ⌈log_3_(N)⌉ by splitting them into groups of three recursively. Is this true for all N, not jus those of the from 3^k and if so, can we do better?

---

Unless you have any extra information about the input, ⌈log_3_(N)⌉ is the best you can reach. Three groups of equal number of coins, weigh two of them against each other, and you'll see which of the three groups has the lower weight. Recursively apply the same algorithm to the lightest group. Any left-over coins above k^3 is also kept for later rounds.

---

Let us say, you have N coins.

Make 3 groups of coins each containing floor(N/3) coins. If there are leftover coins (N%3) , place them in the last(3rd) group. Note that the first 2 groups have same number of coins.

Weigh the 1st group with the 2nd group. If they are unequal, then we have to find the culprit(counterfeit coin) from one of these groups. So our solution space reduces to N/3 after the first weighing .

If they are equal, then the counterfeit coin is present in the 3rd group which has at max (N/3) + 2 coins .

Doing this recursively, lets us find the counterfeit in ceil(log_3_(N)) time .

---

我已经使用了这个代码，但是有时它会被1（（：

def how_many_measurements(n):
    import math
    if n<2:
        x = 0
    elif n >= 2 and n<=4:
        x = 1
    elif n>4 and n<12:
        x = 2
    else:
        x= math.ceil(math.log((2*n+1),3))
    return x    

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

上一篇: 走有向图

下一篇: 在n个硬币中查找假币的算法