weixin_46307169的博客

原创 找假币问题-2分法 VS 3分法

分治算法-找假币问题-2分法VS3分法找假币问题-2分法 VS 3分法问题：有k枚硬币，其中有一枚假币，假币与真币无外观差异，只是假币的重量稍微大一些。现有一个无砝码称重天平，通过称重的方式找出假币，求最小称重次数解题思路暴力求解求解过程：拿一枚硬币放在天平一头，再不断往另一头放硬币，每次放一枚，直到找出那一枚偏重的硬币计算次数：n = k-12分法求解过程：将所有硬币分成2等份，计算次数：n≈log2kn \approx log_2{k}n≈log2​k次3分法求解过程：计算次数：