在n个硬币中发现假币的算法

Question

所以这是一个经典的问题，在一套硬币中找到一个假币，只使用一个称重天平。为了完整起见,这里有一个这样的问题的例子：

一个著名的例子有九个（或更少）物品，例如硬币（或球），它们的重量相同，除了一个，在这个例子中它比其他的更轻--一个假币（一个奇怪的球）。差别只有在秤上称重才能察觉--但只有硬币本身才能称重。仅用两个称重就能将假币隔离吗？

我们所处理的情况是，只有一枚硬币是假币，而且我们知道它是怎么回事（即，我们知道它较重/较轻）。

我的问题是，对于带有一个假币的n硬币，有没有一个通用的高效算法来解决这个问题的广义版本。我一直在想，到目前为止，我认为如果N的形式是3^k，那么您可以通过将它们递归地拆分为三组来找到log_3_(N)中的假货。对于所有的N，而不是从3^k中的N，都是这样吗？如果是这样，我们能做得更好吗？

Answer 1

除非您有任何关于输入的额外信息，否则log_3_(N)是您所能达到的最好的。三组数量相等的硬币，将其中两个相互称重，你就会看到三组中哪一个的重量较轻。递归地将相同的算法应用于最轻的组。K^3以上的任何剩余硬币也将保留以备以后的回合使用。