当前位置:Gxlcms > mysql > 有2n个硬币和一个天平,其中有两个假硬币一个质量为m+1,一个质

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

时间:2021-07-01 10:21:17 帮助过:37人阅读

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

问题:

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


解答:

假设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)把它挑出来。挑出一个以后另一个也就挑出来了。

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





人气教程排行