問題描述：給出27枚硬幣，它們的各種外觀完全相同，但有一枚硬幣稍重一點，是假幣，我們只有一桿秤，試找到一種便捷的方法找出假幣。

簡單直接的思路是：直接從頭到尾掃描遍歷一趟，找出最大的即可。算法復雜度是$O(N)$，不符合我們這一問題“盡可能少比較次數”的宗旨。

可以優化上述思路。
容易想到二分查找，進而用將硬幣分為2堆+1個，“折半”比較，找出那個特殊的假硬幣。

還可以繼續優化。
我們可以隨機等分成三份，拿出兩組比較，劃分的對稱性更強，查找也更快。
比如9枚硬幣，二分最壞的情況是3次查找?

總結

以上是生活随笔為你收集整理的【算法分析与设计】寻找假币问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。