假币问题

Question

12个硬币（或弹珠）中有一个是假的，假设假币比真币轻。

有天平可以比较硬币（或弹珠）。

可以逐一进行比较并比较所有12个硬币。

更有效的方法是使用减少系数算法。将硬币堆分成两半，在天平上比较这两堆。

减少系数2的Big O为log2n。

还有更高效的减少系数3（log3n）算法，但我还没有找到它。

如果有人能解释它以及为什么它更有效，请告诉我。

- Boris Kleynbok

---

如果你说“大 O”，对数的底数并不重要，因为它只是一个常量因子。O(log₂ n) ≡ O(log₃ n) ≡ O(log n)。 - kennytm

Answer 1

这里的主要思想是在设置测试时使用更多有关问题的知识：如果您将其分成3个而不是两个堆栈，并使用其中两个堆栈（每个堆栈包含相同数量的硬币）进行称重，则可以只有两种情况，因为单个假硬币只能在这三个堆栈中的一个中：

1.) 两边重量 相同 ：假硬币不能在称重的两个堆栈中，因此必须在第三个堆栈中：您将问题空间缩小了1/3

2.) 一侧比另一侧重：由于只有一个假硬币，它必须在重量较轻的那一侧：再次将问题空间缩小到1/3

反复洗涤。

- BrokenGlass

---

这是我偶然发现的最喜欢的问题之一，使用3个砝码是可行的，但我从未想过用“通用算法”来解决它。 顺便说一下，将其分成三部分是开始的方法，根据结果您将需要选择不同的方法。最糟糕的情况当然是当您有一个差异，例如1234“重”的和5678“轻”的情况。需要记住的是，1234不能是“轻”的，5678不能是“重”的。当然9、10、11、12必须都不是。 哦糟了，对不起，我以为这是假币不同（即更轻或更重）的问题。 - Valmond

Answer 2

“减3法则”基于这样一个原理：只需要进行一次比较，就可以将要比较的弹珠组合减少1/3。 将弹珠分成3组，并称重其中2组，例如第1组和第2组。

如果第1组的重量==第2组的重量，则第3组有假弹珠。

如果第1组的重量<第2组的重量，则第1组有假弹珠。

如果第1组的重量>第2组的重量，则第2组中有假弹珠。

当然，这假设最初的弹珠集可以均匀地分成3组。如果不是这种情况，则应将它们均匀地分成3组（每组拥有相同数量的弹珠），并将剩余的（0、1或2个）弹珠放到一边，在比较步骤后将其添加回要考虑的弹珠组中。

- Himadri Choudhury