问题:10个瓶子,每个瓶子1000个药片,每瓶中可能是每片1g,可能是每片0.9g,不确定几瓶是0.9g的,有个秤,精度0.1g,,问称一次怎么确定那些瓶子是0.9g的?
对该题目分解,由于不确定是几瓶,情况比较复杂,我们先从简单的地方开始考虑问题,将问题分解为:
1)热身题:10个瓶子,每个瓶子1000个药片,每瓶中可能是每片1g,可能是每片0.9g,有一瓶是0.9g的,有个秤,精度0.1g,,问称一次怎么确定哪个瓶子是0.9g的?
2)进阶题:10个瓶子,每个瓶子1000个药片,每瓶中可能是每片1g,可能是每片0.9g,有两瓶是0.9g的,有个秤,精度0.1g,,问称一次怎么确定哪两瓶子是0.9g的?
思路解决:
对于问题1),我们考虑只有一个瓶子的药有问题,我们应该如何来解决这个问题,因为只能称一次,所以根本在于如何我们在一次称重中通过得到的结果显示出标记的瓶子的序号,问题来了,只能称一次,如何做?
其实我们知道每片药差0.1g,那么如果第一个瓶子一片,第二个瓶子2片,称出来差的0.1g那么就是第一瓶,0.2g就是第二瓶,所以问题一很容易解决:
分别取1,2,...10片就可以区别
对于问题2),其实在于需要前面的两两组合问题,使得接下来的药片的数目需要区别于前面两种瓶子可能组合的结果
问题二解决:分别取:1,2,4,7,10,13,16...
对于最终的问题,相比大家有思路了,即需要错开前面所有的组合:
问题解决:
分别取:1,2,4,8,16,32...
正好是2的n次方,到第十瓶取2的九次方,此时是512,这也是为啥这个题是1000片,10瓶,因为多一瓶就无法取出1024片了。