找次品问题之二

lulijie

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

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

lulijie

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

ID又被抢注了

称两次可以确定有无次品

小明的马甲

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

小明的马甲

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

lulijie

引入以下表示法：
    用 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次肯定能解决问题。应该还可以再优化称法。

lulijie

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

yzsjw0

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

migl

最多有两个不合格

  看着很复杂~~

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

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

lulijie

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