algorithm - 假币问题

Question

12 个硬币(或弹珠)的经典问题，其中一个是假的。假设假币比真币轻。

有秤来比较硬币(或弹珠)。

可以一一比较，把12枚钱币都比较一下。

使用按因子减少算法可以更有效地做到这一点。也就是将硬币堆除以 2，然后在秤上比较 2 个硬币堆。

减少因子 2 的大 O 是 log2n。

有更有效的减少因子 3 (log3n) 算法，但我还没有找到它。

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

Answer 1

此处的主要思想是在设置测试时使用更多关于问题的知识:如果您分成 3 堆而不是两堆，并对其中两堆(每堆包含相同数量的硬币)进行称重，您假设单个假币只能出现在这三个堆栈中的一个中，则只能有两种情况:

1.) 双方都有相同的重量:假硬币不能在称重的两堆中，所以必须在第三堆中:你将问题空间减少到 1/3

2.) 一侧比另一侧重:因为只有一枚假硬币，所以它一定在重量较轻的一侧:您再次将问题空间减少到 1/3

冲洗并重复。