现有16枚外形相同的硬币,其中有一枚比真币的重量轻的假币,若采用分治法找出这枚假币,至少比较(63

Question

现有16枚外形相同的硬币，其中有一枚比真币的重量轻的假币，若采用分治法找出这枚假币，至少比较（63）次才能够找出该假币。

A.3

B.4

C.5

D.6

Answer 1

正确答案：B
本题考查算法基础知识。用分治法找假硬币的过程为：先将16枚硬币对等分为2堆（各8枚）并比较其重量，假币在较轻的那一堆中；然后将8枚硬币对等分为2堆（各4枚）并比较其重量，假币在较轻的那一堆中；再将4枚硬币对等分为2堆（各2枚）并比较其重量，假币在较轻的那一堆中；最后比较两个硬币的重量，找出假币。因此，至少比较4次才能够找出该假币。