用于查找从一组 n 个球中查找缺陷球所需的最小权重数的算法
好吧，这是我经常遇到的一个难题 - 给定一组 12 个球，其中一个有缺陷（重量要么更轻，要么更重）。您可以称重 3 次，找出有缺陷的部分，并判断哪个重量更轻或更大。
这个问题的解决方案是存在的，但我想知道我们是否可以通过算法确定如果给定一组“n”个球，则需要使用梁天平确定哪个球有缺陷以及如何（较轻或较重）。
Okay here is a puzzle I come across a lot of times-
Given a set of 12 balls , one of which is defective (it weighs either less or more) . You are allow to weigh 3 times to find the defective and also tell which weighs less or more.
The solution to this problem exists, but I want to know whether we can algorithmically determine if given a set of 'n' balls what is the minimum number of times you would need to use a beam balance to determine which one is defective and how(lighter or heavier).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Jack Wert 的精彩算法可以在这里找到
（如描述的情况 n 的形式为 (3^k-3)/2，但它可以推广到其他 n，请参阅下面的文章
）更短的版本，可能更易读的版本在这里
对于 (3^k-3)/2 形式的 n，上述解决方案完全适用，所需称重的最小次数为 k。
在其他情况下...
为所有 n 调整 Jack Wert 的算法。
为了针对所有 n 修改上述算法，您可以尝试以下操作（不过，我还没有尝试证明其正确性）：
首先检查 n 是否属于 (3^k-3)/2。如果是，则应用上述算法。
如果不是，
如果n = 3t（即n是3的倍数），你会发现至少m> 1。 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）进行称重。
A wonderful algorithm by Jack Wert can be found here
(as described for the case n is of the form (3^k-3)/2, but it is generalizable to other n, see the writeup below)
A shorter version and probably more readable version of that is here
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).
三分法！ ：）
解释 ：
给定一组 n 个球，将其细分为 3 组 A、B 和 C，每组有 n/3 个球。
比较A和B，如果相等，则缺陷球在C中。
所以
，你的最小次数就是你能将 n 除以三的次数（抱歉，我不知道这个词的英文单词）。
Trichotomy ! :)
Explanation :
Given a set of n balls, subdivide it in 3 sets A, B and C of n/3 balls.
Compare A and B. If equal, then the defective ball is in C.
etc.
So, your minimum number of times is the number of times you can divide n by three (sorry, i do not know the english word for that).
您可以使用通用规划算法：http://www.inf.ed .ac.uk/教学/课程/计划/
You could use a general planning algorithm: http://www.inf.ed.ac.uk/teaching/courses/plan/