在n个硬币中查找假币的算法
所以这就是仅使用称重天平在一组硬币中找出假币的经典问题。 为了完整起见，下面是这样一个问题的一个例子：
一个众所周知的例子有九个（或更少的）物品，例如硬币（或球），除了一个之外重量相同，在这个例子中比其他人更轻 - 伪造（古怪的）。 这种差异只有通过称重才能被察觉 - 但只有硬币本身可以被称重。 仅用两次称重就可以隔离假币吗？
我们正在处理的情况是，只有一个硬币是伪造的，我们知道它是如此（即我们知道它是重量更轻/更轻）。
我的问题是，是否有一个通用的高效算法来解决这个问题的N硬币与一个伪造品的通用版本。 我一直在想它，到目前为止，如果N的形式为3^k ，那么你可以通过将它们分成三组来递归地在“ ⌈log_3_(N)⌉找到伪造品。 这对所有的N都是如此，不是从3^k ，如果是的话，我们可以做得更好吗？
除非您有任何关于输入的额外信息， ⌈log_3_(N)⌉是您可以达到的最佳信息。 三组相同数量的硬币重量相互对峙，你会看到三组中哪一组的重量较轻。 递归地将相同的算法应用于最轻的组。 任何高于k^3剩余硬币也将保留以备后用。
让我们说，你有N个硬币。
制作3组硬币，每个硬币都含有地板（N / 3）硬币。 如果有剩余硬币（N％3） ，请将它们放在最后（第三）组。 请注意，前两组有相同数量的硬币。
称第二组为第一组。 如果他们不平等，那么我们必须从这些团体中找到罪魁祸首（假币）。 所以我们的解决方案空间在第一次称量后减少到N / 3 。
如果它们相同，那么伪造的硬币出现在具有最大（N / 3）+2个硬币的第三组中。
以递归方式执行此操作，让我们在ceil（log_3_（N））时间内找到伪造品 。
我已经使用了这个代码，但是有时它会被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