Skip to content

Latest commit

 

History

History
12 lines (10 loc) · 871 Bytes

File metadata and controls

12 lines (10 loc) · 871 Bytes

问题

有100枚硬币,其中1枚重量与众不同,是假币,略轻一些。如果用天平秤,请问至少称几次一定能找到这枚假币。

分治解法

  1. 将100硬币分成3份,33,33,34。
  2. 称量1、2份,若天平平衡,则假币必在另外34枚中。若不平衡,假币在轻的那33枚里。
  3. 将34枚分为11/11/12枚(或将33枚分成11*3)。
  4. 称量两组11枚的硬币,若平衡,假币在12枚里(或另外的11枚)若不平衡,假币在轻的11里。
  5. 将11(或12)枚分成3/4/4(或4/4/4),称量4/4,方法同上。
  6. 将剩下的3(或4)分为1/1/1(或1/1),称量1/1,若平衡,则剩下的一枚是假币,若不平衡,轻的是假币。 若还剩4枚,出现1/1平衡,剩下2枚则称量,显然轻的是假币。

这种方法只需要5次就能解决这个问题。