找次品问题之二

lulijie

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

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次肯定能解决问题。应该还可以再优化称法。

小明的马甲

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

小明的马甲

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

ID又被抢注了

称两次可以确定有无次品

lulijie

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