在 n 个硬币中找到假币的算法

Question

这就是仅使用称重天平从一组硬币中找出假币的经典问题。为了完整起见，这里是此类问题的一个示例:

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?

我们正在处理只有一枚硬币是假币的情况，并且我们知道这是怎么回事(即我们知道它更重/更轻)。

我的问题是，对于 N 硬币和一枚假币，是否有通用有效的算法来解决此问题的一般版本。我一直在考虑它，到目前为止我已经知道如果 N 是 3^k 的形式，那么你可以在 ⌈log_3_(N )⌉ 通过递归地将它们分成三组。这是否适用于所有 N，而不仅仅是来自 3^k 的那些 N，如果是这样，我们可以做得更好吗？

Answer 1

除非您有关于输入的任何额外信息，否则 ⌈log_3_(N)⌉ 是您能达到的最佳结果。三组相同数量的硬币，将其中两组相互称重，您会看到这三组中哪一组的重量较小。递归地将相同的算法应用于最轻的组。任何超过 k^3 的剩余硬币也将保留以备后几轮使用。