12砝码称重问题.docx

1. 实验室管理员有12枚同样标度值的砝码,其中有一枚重量不合格的,管理员不小心把不合格的砝码与合格的混在一起了,从外观看不出哪枚砝码不合格,也不知道不合格砝码比合格的重还是轻,只知道与合格砝码重量有少许的差别。现在管理员准备用比较天平两边轻重的方法来找出不合格砝码。为了称出哪枚是不合格砝码,至少要称多少次?(需说明应用的系统理论,写出解题步骤)(5分)
答:应用的系统理论是信息论。
考虑随机事件“12枚同样标度值的砝码,其中有一枚重量不合格”的概率P=1/12,
再考虑随机事件“不合格砝码比合格的重还是轻”的概率P=1/2
上述两事件是相互独立的,同时发生的概率为P=1/24
上述两事件的联合不确定性,用信息量表示:
用天平称量,可以减少不确定性,每次称量两个或两堆(每堆中砝码个数相同)有三个结果:轻,相等,重。各种可能出现的概率都是1/3,因此,每次称量可以减少的不确定性用信息量表示:
由此,可以推断需要称量的次数是()/()=<=3
如何称重,.
我网上很早之前看过这个例子,,知道用多少次就能找出不合格砝码.
另外,班上的高手很多的,请哪位用归纳法总结个“n个砝码中找出一个假的”一般规律。
http://hi./jiyanmoyu/blog/item/
今晚和一湖大ACM队员聊天,他描述了个古老的砝码称重问题,题意如下:
一个很古老的问题,不是acm的;
题目是这样的:现有十二枚金币,其中有一枚是假的(有可能比真的重,也可能比真的轻),现有一座没砝码的天平,只能称三次,是确定假的那一枚
要确定这一枚并不容易,因为只能用三次称重,经我
反复思量,认为以下方法是可行的。
首先将砝码编一下号吧,就从1到12,也方便我们描述。
第一次就是分三组,每组4个金币,1-4一组,5-8一组,9-12一组,那么可以:
将1-4与5-8放于天平左右两边,可能的结果为:
(第一次称重后)1-4与5-8相等,说明假金币必在9-12中,两称重确定4个金币中的一个很简单:将10与11放在天平称一次,若相等,则假的必在9与12之间,将10与9放在天平两边称一次即确定了,若10与11不等,那么将9与10放在天平两边称一次就可能确定了,刚好三次。
(第一次称重后)1-4轻,5-8重,接下来的处理就比较有技巧了,可能不好想到,但还是容易懂的。
我们将1,2,5三个金币先放一边,在9-12中(9-12中的金币肯定是好的,真的)随便拿一个,比如说9,而且将3,4与6,7,8中各