魔方吧·中文魔方俱乐部

标题: 找次品问题之二 [打印本页]

作者: lulijie 时间: 2010-5-7 21:50:57 标题: 找次品问题之二

某车间生产了一个批次的砝码，共81个，已知其中最多有两个不合格（重量不符）。
现在使用一架天平，最多称几次，可以确定这批货是否有次品。
如果要找出这些次品，又需要称多少次？

[ 本帖最后由 lulijie 于 2010-5-7 21:52 编辑 ]

作者: superacid 时间: 2010-5-7 22:08:52

两个貌似不太好办...

作者: yq_118 时间: 2010-5-7 22:25:14

要是两个的重量和正常就惨了。

作者: lulijie 时间: 2010-5-7 22:29:27

称80次肯定能找出次品。有没有次数更少的？

作者: limite034 时间: 2010-5-7 22:31:23

这题，好像在百度里面出现过。是因为在魔友给的找次品之一的链接，我似乎看到的。待假以时日，我再搜搜。看看两道题是否是一个层面习题

作者: 铯_猪哥恐鸣 时间: 2010-5-8 01:27:28

不会少于7次，正在思考七次是否可能。。。

作者: abc 时间: 2010-5-8 21:06:33

不知楼主考虑过下面几种情况吗？1、如果两个次品一样重(或轻或重）；2、两个次品不一样重(都重于或都轻于标准砝码），3、一个重于标准砝码，一个轻于标准砝码，加起来不等于两个标准砝码的重量；4、一轻一重，而加起来正好是两个标准砝码的重量。

[ 本帖最后由 abc 于 2010-5-9 08:31 编辑 ]

作者: lulijie 时间: 2010-5-9 11:04:12

7楼提的各种情况都需要考虑到。

作者: migl 时间: 2010-5-10 13:07:36

最多有两个不合格

看着很复杂~~

光两个的就有五种：
1. 两个都“重” （细分为：都一样“重”和不一样“重” ）；
2. 两个加起来“重”；（一重一轻）
3. 两个加起来“等”；（一重一轻）
4. 两个加起来“轻”；（一重一轻）
5. 两个都“轻” （细分为：都一样“轻”和不一样“轻” ）。

另外还要权衡有零个、一个或两个不合格。

作者: yzsjw0 时间: 2010-5-10 18:51:36

如谁将此题完全解决，则将“称球问题”向前推进了一大步。估计楼主还没有完全的答案吧？

作者: lulijie 时间: 2010-5-10 19:15:35

目前没有最优的答案。
现在我只有称80次的方法。如果谁有比80次少的方法，欢迎发表。

作者: lulijie 时间: 2010-5-10 20:05:46

引入以下表示法：
用 a,b=c,d 表示天平左边放有砝码a和b，天平右边放有砝码c和d，= 表示天平两边平衡，> 表示天平左边重，< 表示天平右边重。
-----------------------------------------------------------------------------------------------
题目的一般化：一共有N个砝码，其中最多有2个不合格。
----------------------------------------------------------------------------------
N=10时，用下面的方法可以大大减少称的次数。
给砝码编号 1,2,3,4,5,6,7,8,9,0
   天平只要不平衡，马上就可确定存在不合格的砝码。所以只有称的过程中天平一直平衡，才是次数最多的称法。
第1次称：1,2 =3,4
第2次称：1,5 =2,6
第3次称：3,7=5,8
第4次称：7,9=1,0
第5次称：7=9 10个砝码都是正常
      或7<>9  那么9,0砝码不合格。
   --------
   最多5次称可解决N=10的问题
-----------------------------------------------------
所以按照上面的方法，N=81时，41次肯定能解决问题。应该还可以再优化称法。

作者: 小明的马甲 时间: 2010-5-10 21:23:15

我先抛个砖吧，对于球数为：2^k-1,k>2的情况
测量方案将所有球编号，1,2,3...并用二进制表示：1,10,11...第i次天平的两边放编号的第i位为1的球
用这个方案满足：每个球都被称过；不同的任何两个球的称量序列互不相同。
于是，若只有一个球坏，答案显然。若有两个球，同样的可以得到出错条件需要在所有的称量中他们同时出现或不出现，这是不可能的。

作者: 小明的马甲 时间: 2010-5-10 21:25:14

另外对于3^(k-1)-1个球，我也找到了k次的解答，思路类似的

作者: ID又被抢注了 时间: 2010-5-11 14:06:47

称两次可以确定有无次品

作者: lulijie 时间: 2010-5-11 16:36:45

确定有无次品，13楼的方法显而易见是可行的，不过如果不是2^k-1类型的，第i位为1的球
的个数可能会是奇数个，这样天平不能称重，需要加入一个正常球，才能称重。细节上需要考虑如何处理此种情况。
14楼的情况，我考虑了一下，也应该是可行的。不过与13楼的情况稍有不同，最好给出你的具体方案。
--------------------------------------
还有:如果要找出具体的次品，上述方法还不知是不是最少步数的方法.

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)