关于找到假硬币的算法问题,2个假币怎么算?
有2n个硬币和一个天平,其中有一个质量为m+1,一个质量为m-1,其余质量都为m,用O(logn)的时间复杂度找到这两个假硬币。这个应该怎么做。
想了很久没想出来怎么做,问题应该是用分治的方法做,我有如下假设,假设两个假币在分的过程中始终在一起,那原问题就成了n个硬币,每个硬币质量2m,找到其中满足某条件的一个硬币,这怎么用O(log)实现。
[解决办法]
假设2n有k个2进制位。设计k次称量,第i(i=1~k)次是把二进制序号第i位为0的硬币给取出来称。
这样第i次称量的结果如下,左边2列是偏重偏轻的硬币的序号在第i列的二进制值,第3列是第i次称量结果
0 0 正常
0 1 偏轻
1 0 偏重
1 1 正常
经过这k次称量,偏重偏轻的如果同一个二进制位数码不同的话那个位上的值已经知道了。
接下来,假设第m位是刚才求出来的序号不同的那一位(这样的位一定存在,否则两枚硬币序号就会相同)。再做k次称量,这次,第i次挑选的硬币是第i位位0并且第m位为0。这样相当于排除了其中一枚硬币以后再O(logn)把它挑出来。挑出一个以后另一个也就挑出来了。