《《找次品问题》方法.docx》由会员分享，可在线阅读，更多相关《《找次品问题》方法.docx（4页珍藏版）》请在三一文库上搜索。
1、找次品问题方法找次品问题的求解方法还就是从比尔盖茨与81 个玻璃球的问题说开来吧。(1)小比尔盖茨的问题: 这儿有 81 个玻璃球 , 其中有一个球比其她的球稍重, 如果只能用天平来测量, 至少要称多少次才能保证找出来呢？(2) 如果不知道次品玻璃球与标准球的轻重 , 同样只用天平来测量 , 至少要称多少次才能保证找出次品玻璃球来？怎样用天平来测量次品？就就是要用天平称量时的“平衡” 与“不平衡” 来判断研究对象的情况。“平衡”判明没次品; “不平衡”判明次品就在这里。本题要求最少的称量次数 , 显然还要找出一个解决问题的最优策略, 也就就是要让天平每称量一次能判断的研究对象个数最多 , 最终
2、达到称量次数最少的目的。 实际操作起来就就是把 研究对象怎样分组 , 分成多少组的问题。怎样分组？有平均分( 对于不能平均分的数量 , 让数量多的组多1 个 , 少的组少 1个 ),任意分两种分法。 比较起来只有平均分才能让“平衡” 与“不平衡” 说明研究对象的情况( 任意分时 , 天平两边数量不等 , “平衡”已不可能, “不平衡”也不能判断出问题), 所以选择平均分法。分成多少组？有分成2 组、 3 组、 4 组、 5 组等多种分法。因为天平有两个托盘, 每称量一次能放上两组研究对象, 最多能判断出3 组的情况 ( 既能判断出天平上两组的情况, 还能判断出天平外一组的情况。若平衡 , 次品
3、就在盘外那组中 ; 若不平衡 , 盘外那组中就无次品 ),所以只有分成 2 组或 3组才能使天平每称量一次包括研究对象的全部, 其她组数达不到这个要求舍弃。 再比较2 组分法、 3 组分法的优劣 : 把 2 组分法、 3 组分法上次称量判断出的问题组对象再分别 2 等分之、 3 等分之。可以得出下次称量时天平每边的对象数量,3 组分法的远比 2 组分法的少。继续称量下去, 显然 ,3组分法的称量次数要少, 更符合最优策略。综合起来 , 就就是选择 平均分成3 组的分法。用天平称量的方法找次品有什么规律？因为采用的就是三等分法, 则每次称量都就是把上次找出的问题组对象三等分之进行研究 , 且最后
4、一次找出次品时, 天平两边各只有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 次最多只能判断出
5、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 个玻璃球 , 其中有一个
6、球比其她的球稍重 ,如果只能用天平来测量 , 至少要称多少次才能保证找出来呢？因为 81=34, 所以最少要称 4 次才能保证找出次品。问题 (2)如果不知道次品玻璃球与标准球的轻重, 同样只用天平来测量 , 至少要称多少次才能保证找出次品玻璃球来？先测出次品玻璃球就是重了还就是轻了:分组81 3=27(27,27,27)1 次任取两组过天平, 有“平衡”与“不平衡”两种情况。研究“平衡”情况既就是“平衡”, 就判断出次品在天平外那组中。2 次任取已过天平一组与天平外那组同称, 肯定不平衡。 若原天平外那组重些, 就判断出次品比标准球重, 否则 , 次品就就是比标准球轻。研究“不平衡” 情况既
7、就是 “不平衡” , 就判断出次品已在天平中, 天平外那组就是标准球。2 次取较重的一组与天平外那组同称, 有“平衡”、 “不平衡”两种可能。若“平衡”就判断出次品球比标准球轻; 若“不平衡”就判断出次品球比标准球重。综合以上研究得出: 最少称 2 次才能知道次品球在那组中, 也才能知道次品球比标准球就是重些还就是轻些。此时, 次品所在组有球27 个。因为 ,27=3 , 所以最少再称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)