标签云

微信群

扫码加入我们

WeChat QR Code

算法找出假币在n个硬币

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 (i.e. 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?


I'm voting to close this question as off-topic because belongs to programming.stackexchange.com or maths.stackexchange.com

1970年01月01日00分03秒

DhruvPathak Explain. I'm asking about the specific algorithm we could use; how is that not related to stackoverflow. See here and here and here...

2018年05月24日10分30秒

Why are you voting this as off-topic? This is about designing an algorithm, which would be equally valid on other sites, and perhaps a better fit on maths, but it's also on topic here.

2018年05月23日10分30秒

You say average case. What would be the best and worst cases then?

2018年05月23日10分30秒

For random input, ⌈log_3_(N)⌉ is the best, average and worst complexity. In the worst case, we get 2 coins left over, which we cannot check, until we reach the end. This adds at most one extra comparison at the end. The actual worst-case complexity would be ⌈log_3_(N)⌉ * 2 + 1, for keeping the 2 extra coins around.

2018年05月23日10分30秒

Why is it off by one?

2018年05月23日10分30秒

Not sure. For some randomly generated number of coins it is.

2018年05月23日10分30秒