找到从一组n个球中找到缺陷球所需的最小加权数的算法

Question

好的,这是我经常遇到的一个难题 - 给定一组12个球,其中一个有缺陷(重量更轻或更多).允许您重量3次以找到有缺陷,并告知哪个重量更轻或更多.

这个问题的解决方案存在,但我想知道我们是否可以通过算法确定是否给定一组"n"球,你需要使用波束平衡来确定哪一个有缺陷以及如何(更轻或更重).

Answer 1

可以在这里找到Jack Wert的精彩算法

• http://www.cut-the-knot.org/blue/OddCoinProblems.shtml

（如n的情况描述为（3 ^ k-3）/ 2的形式，但可以推广到其他n，请参见下面的内容）

A shorter version and probably more readable version of that is here

• http://www.cut-the-knot.org/blue/OddCoinProblemsShort.shtml

For n of the form (3^k-3)/2, the above solution applies perfectly and the minimum number of weighings required is k.

In other cases...

Adapting Jack Wert's algorithm for all n.

In order to modify the above algorithm for all n, you can try the following (I haven't tried proving the correctness, though):

First check if n is of the from (3^k-3)/2. If it is, apply above algorithm.

If not,

If n = 3t (i.e. n is a multiple of 3), you find the least m > n such that m is of the form (3^k-3)/2. The number of weighings required will be k. Now form the groups 1, 3, 3^2, ..., 3^(k-2), Z, where 3^(k-2) < Z < 3^(k-1) and repeat the algorithm from Jack's solution.

Note: We would also need to generalize the method A (the case when we know if the coin is heavier of lighter), for arbitrary Z.

If n = 3t+1, try to solve for 3t (keeping one ball aside). If you don't find the odd ball among 3t, the one you kept aside is defective.

If n = 3t+2, form the groups for 3t+3, but have one group not have the one ball group. If you come to the stage when you have to rotate the one ball group, you know the defective ball is one of two balls and you can then weigh one of those two balls against one of the known good balls (from among the other 3t).