假硬幣問題

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）彈珠放在一邊，並將它們添加回必須考慮的彈珠組在比較步驟之後。