从一组 n 个球中找出有缺陷的球所需的最小权重数的算法

Question

好吧，这是一个我遇到过很多次的谜题——给定一组 12 个球，其中一个有缺陷(它的重量或轻或重)。您可以称重 3 次以找出有缺陷的产品，并判断哪个重量更轻或更重。

这个问题的解决方案是存在的，但我想知道我们是否可以通过算法确定如果给定一组“n”个球，您需要使用平衡梁来确定哪个球有缺陷的最少次数是多少以及如何(更轻或更重)。

Answer 1

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

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

(如案例所述，n 的形式为 (3^k-3)/2，但它可以推广到其他 n，请参阅下面的文章)

这里有一个较短的版本，可能更易读

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

对于形式为 (3^k-3)/2 的 n，上述解决方案完全适用，所需的最小称量次数为 k。

在其他情况下...

---

为所有 n 调整 Jack Wert 的算法。

为了对所有 n 修改上述算法，您可以尝试以下方法(虽然我还没有尝试证明正确性):

首先检查 n 是否来自 (3^k-3)/2。如果是，应用上面的算法。

如果没有，

如果 n = 3t(即 n 是 3 的倍数)，您会找到最小的 m > n 使得 m 的形式为 (3^k-3)/2。所需的称重次数将为 k。现在形成组 1, 3, 3^2, ..., 3^(k-2), Z，其中 3^(k-2) < Z < 3^(k-1) 并重复 Jack 的算法解决方案。

注意:对于任意 Z，我们还需要推广方法 A(当我们知道硬币是重还是轻时的情况)。

如果 n = 3t+1，尝试求解 3t(将一个球放在一边)。如果您在 3 吨中没有找到奇数球，则您放在一边的那个是有缺陷的。

如果n = 3t+2，组成3t+3组，但有一组没有一个球组。如果您在必须旋转一个球组时来到舞台，您知道有缺陷的球是两个球之一，然后您可以将这两个球中的一个与已知的好球之一(来自其他 3t)进行称重.