算法找到所需的权重最小的号码找到有缺陷的球从一组N个球 [英] Algorithm to find minimum number of weightings required to find defective ball from a set of n balls
问题描述
好这里是一个谜我遇到了很多的时间─的 给定一组的12个球，其中之一是有缺陷的（它的重量或者更小或更大）。您允许重达3次发现有缺陷的，也知道它的重量少跌多。
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.
解决这个问题的存在，但我想知道我们是否能够通过算法确定给定一组'N'球是什么时候，你就需要使用束平衡，以确定哪一个是有缺陷的最小数量以及如何（更轻或更重）。
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).
推荐答案
一个美妙的算法由Jack WERT可以在这里找到
A wonderful algorithm by Jack Wert can be found here
（如描述的情况，n为的形式（3 ^ K-3）/ 2的，但它是推广到另一个n，请参阅下面的书面记录）
(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
有关n中的形式的（3 ^ K-3）/ 2，在上述溶液内完全和所需称量的最小数目为k
For n of the form (3^k-3)/2, the above solution applies perfectly and the minimum number of weighings required is k.
在其他情况下...
适应杰克WERT的算法对所有的n。
为了修改上述算法对所有的n，你可以试试下面的（我没有尝试过证明的正确性，虽然）：
In order to modify the above algorithm for all n, you can try the following (I haven't tried proving the correctness, though):
如果首先检查n是的，从（3 ^ K-3）/ 2。如果是，应用上述算法
First check if n is of the from (3^k-3)/2. If it is, apply above algorithm.
如果没有，
如果N =3吨（即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），并重复杰克的解决方案的算法。
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.
请注意：我们还需要推广方法A（的情况下，当我们知道，如果硬币是较轻较重），任意ž
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.
如果N = 3T + 1，尽量解决的3吨（保持一球除外）。如果您没有找到3吨之间的奇数球，你扔在一边的一个是有缺陷的。
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.
如果N = 3T + 2，形成群体为3T + 3，但有一组没有一球组。如果你走不到当你旋转一球组，你知道有缺陷的球是两个球一个，然后你可以权衡这两个球中的一个针对已知良好的球之一（从另一个3吨中）
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个球的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
