假硬币问题

Question

经典问题与12硬币（或弹子）其中之一是假的。假币比假币轻。

有比较硬币（或弹子）的比例。

一个可以做比较一个一个比较所有12个硬币。

更高效地使用Decrease By Factor算法可以做到这一点。其中硬币堆栈分为2和比较2个堆栈。

减少系数2的大O为log2n。

通过因子3（log3n）算法可以更有效地减少，但我还没有找到它。

如果有人解释它，为什么它更高效让我知道。

Answer 1

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

1.）双方有相同重量：假币不能在两个堆叠中称重，所以必须在第三步：你将问题空间减少到1/3

2.）一方重量比另一方重：因为只有一枚假币，它必须位于重量的一侧s：再次将问题空间减少到1/3

冲洗并重复。

Answer 2

“减少3”算法的工作原理是，只需进行1次比较，就可以减少三分之一的弹珠比例。

拆分弹珠分为3组，并且将它们的权重2，说组1和2

1. 如果重组2然后组3的组1 ==重量的具有假大理石
2. 如果重组1 <重量组2的组然后1具有假大理石
3. 如果重组1的>重量组2的组然后2具有假大理石

当然，这假定吨他原来的一套弹珠可以平均分成3组。如果不是这种情况，那么均匀分成3组（每组有相同数量的弹珠），并将剩余的（0,1或2）弹珠放在一边，并将它们添加回必须考虑的弹珠组在比较步骤之后。