《找次品问题》方法.doc

《找次品问题》的求解方法              还就是从比尔·盖茨与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个研究对象开始逆推找规律。      天平称量法找次品统计表次数最多判断出研究对象的个数13=31                 (1,1,1)23×3=9=32        (3,3,3)(1,1,1)39×3=27=33      (9,9,9)(3,3,3)(1,1,1)427×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)