有2n个硬币和一个天平，其中有两个假硬币一个质量为m+1，一个质

问题： 有2n个硬币和一个天平，其中有一个质量为m1，一个质量为m-1，其余质量都为m，用O(logn)的时间复杂度找到这两个假硬币？ 解答： 假设2n有k个2进制位。设计k次称量，第i(i=1~k)次是把二进制序号第i位为0的硬币给取出来称。 这样第i次称量的结果如下，左

问题：

有2n个硬币和一个天平，其中有一个质量为m&＃43;1，一个质量为m-1，其余质量都为m，用O(logn)的时间复杂度找到这两个假硬币？

解答：

假设2n有k个2进制位。设计k次称量，第i(i=1~k)次是把二进制序号第i位为0的硬币给取出来称。

1 1 正常

接下来，假设第m位是刚才求出来的序号不同的那一位（这样的位一定存在，否则两枚硬币序号就会相同）。再做k次称量，这次，第i次挑选的硬币是第i位位0并且第m位为0。这样相当于排除了其中一枚硬币以后再O(logn)把它挑出来。挑出一个以后另一个也就挑出来了。

举例：例如有2*3 = 8个硬币，所以k=3（如果2n为14 ，则选取k=4）。对每个硬币编码：000 001 010 011 100 101 110 111。 则先称出个位为零的硬币是不是4m（有四个零），再十位.... 以此类推。。。便可在O(logn)时间内找出假硬币。。。