上QQ阅读APP看书,第一时间看更新
5.乒乓球中的次品
有100盒乒乓球,每盒中有乒乓球100个,共计10000万个乒乓球。假定每个乒乓球上都有编号,如下:
001-001,001-002……001-100
……
100-001,100-002……100-100
按要求,本批次的乒乓球单个重量应该为1克(假定数据,可能与事实不符),可由于生产失误,其中混入了一盒次品,该盒乒乓球中的100个球重量均为1.1克。现在给你提供一个足够大且足够精确的电子秤,请问你最少称重多少次可以找到这盒次品?
(提示:每盒都可以拆开)
正常人的解题思路:
最优方案:折半查找法。即:
第一次:放001~050这50盒,如果重量正好,那么次品在另外的50盒中。
第二次:放051~075这25盒,如果重量正好,那么次品在另外的25盒中。
以此类推。
答案是:7次。
这个答案似乎看上去已经是最佳方案了。
但是仔细观察题目,发现有好多已知条件没有用。比如为什么要给乒乓球编号,而不是给盒子编号?为什么说可以拆开?