标签云

微信群

扫码加入我们

WeChat QR Code

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...

2019年05月22日42分55秒

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.

2019年05月22日42分55秒

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

2019年05月22日42分55秒

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.

2019年05月22日42分55秒

Why is it off by one?

2019年05月22日42分55秒

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

2019年05月22日42分55秒