聚热点 juredian

《找次品问题》的求解方法

《找次品问题》的求解方法

湖南衡东 许岳飞

还是从比尔·盖茨与81个玻璃球的问题说开来吧。

(1)小比尔·盖茨的问题:这儿有81个玻璃球,其中有一个球比其他的球稍重,如果只能用天平来测量,至少要称多少次才能保证找出来呢?

(2)如果不知道次品玻璃球与标准球的轻重,同样只用天平来测量,至少要称多少次才能保证找出次品玻璃球来?

怎样用天平来测量次品?就是要用天平称量时的“平衡”与“不平衡”来判断研究对象的情况。“平衡”判明没次品;“不平衡”判明次品就在这里。本题要求最少的称量次数,显然还要找出一个解决问题的最优策略,也就是要让天平每称量一次能判断的研究对象个数最多,最终达到称量次数最少的目的。实际操作起来就是把研究对象怎样分组,分成多少组的问题。

怎样分组?有平均分(对于不能平均分的数量,让数量多的组多1个,少的组少1个),任意分两种分法。比较起来只有平均分才能让“平衡”与“不平衡”说明研究对象的情况(任意分时,天平两边数量不等,“平衡”已不可能,“不平衡”也不能判断出问题),所以选择平均分法。

分成多少组?有分成2组、3组、4组、5组等多种分法。因为天平有两个托盘,每称量一次能放上两组研究对象,最多能判断出3组的情况(既能判断出天平上两组的情况,还能判断出天平外一组的情况。若平衡,次品就在盘外那组中;若不平衡,盘外那组中就无次品),所以只有分成2组或3组才能使天平每称量一次包括研究对象的全部,其他组数达不到这个要求——舍弃。再比较2组分法、3组分法的优劣:把2组分法、3组分法上次称量判断出的问题组对象再分别2等分之、3等分之。可以得出下次称量时天平每边的对象数量,3组分法的远比2组分法的少。继续称量下去,显然,3组分法的称量次数要少,更符合最优策略。

综合起来,就是选择平均分成3组的分法。

用天平称量的方法找次品有什么规律?

因为采用的是三等分法,则每次称量都是把上次找出的问题组对象三等分之进行研究,且最后一次找出次品时,天平两边各只有1个研究对象,所以从天平两边各放1个研究对象开始逆推找规律。

天平称量法找次品统计表

次数

最多判断出研究对象的个数

1

3=31(1,1,1)

2

3×3=9=32(3,3,3)(1,1,1)

3

9×3=27=33(9,9,9)(3,3,3)(1,1,1)

4

27×3=81=34(27,27,27)(9,9,9)

(3,3,3)(1,1,1)

一般地,用天平称量n次,能判断出研究对象的最多个数Y=3n。

上面研究的都是“最多”数量的情况,不满足“最多”条件的数量情况如何呢?比如4、12情况怎样?

先研究4:因为天平称量1次最多只能判断出3个,所以要再称量1次,一共2次才能有保证。[平衡2次:(2,1,1)→(1,1)。不平衡1次:(2,1,1)。]

再研究12:天平称量2次最多能判断出9个,所以也要再称1次,一共是3次才能有保证。[平衡3次:(4,4,4)→(2,1,1)→(1,1)。不平衡2次:(4,4,4)→(2,1,1)]

一般地,用天平称量法找次品,当研究对象的个数Y满足关系式3n-1<Y≤3n时,最少要称量n次才能保证找出次品。

现在回头解答比尔·盖茨与81个玻璃球的问题。

问题(1)小比尔·盖茨的问题:这儿有81个玻璃球,其中有一个球比其他的球稍重,如果只能用天平来测量,至少要称多少次才能保证找出来呢?

因为81=34,所以最少要称4次才能保证找出次品。

问题(2)如果不知道次品玻璃球与标准球的轻重,同样只用天平来测量,至少要称多少次才能保证找出次品玻璃球来?

先测出次品玻璃球是重了还是轻了:

分组81÷3=27(27,27,27)

1次——任取两组过天平,有“平衡”与“不平衡”两种情况。

研究“平衡”情况既是“平衡”,就判断出次品在天平外那组中。

2次——任取已过天平一组与天平外那组同称,肯定不平衡。若原天平外那组重些,就判断出次品比标准球重,否则,次品就是比标准球轻。

研究“不平衡”情况既是“不平衡”,就判断出次品已在天平中,天平外那组是标准球。

2次——取较重的一组与天平外那组同称,有“平衡”、“不平衡”两种可能。若“平衡”就判断出次品球比标准球轻;若“不平衡”就判断出次品球比标准球重。

综合以上研究得出:最少称2次才能知道次品球在那组中,也才能知道次品球比标准球是重些还是轻些。此时,次品所在组有球27个。因为,27=33,所以最少再称3次才能保证找出次品球来。

一共是2+3=5(次)

例:若73个零件,其中有一个比其他的零件稍重,如果只能用天平来测量,至少要称多少次才能保证找出来呢?

解:因为33<73≤34,所以最少要称4次才能保证找出次品。

[平衡4次:(25,24,24)(9,8,8)(3,3,3)(1,1,1)。不平衡4次:(25,24,24)(8,8,8)(3,3,2)(1,1,1)]

搜索建议:《找次品问题》的求解方法  
热博

 春天的脚步声作文

春天的脚步声作文在学习、工作或生活中,大家一定都接触过作文吧,作文一定要做到主题集中,围绕同一主题作深入阐述,切忌东拉西扯,主题涣散甚至无主题。如何写一篇有思想...(展开)

热博

 情人节是什么时间?

12个月,每个月都有情人节,具体时间如下: 1、1月14日 日记情人节。 2、2月14日 传统情人节。 3、3月14日 白色情人节。 4、4月14日 黑色情人节...(展开)