找到不同重量的球所需的最小重量是多少?[关闭]

如果 3^x = N 球和 x -- number of weighs , x = log3(N) ;

3^x = 3^45 - 3^40;
3^x = 3^40 * (3^5 - 1);
x = log3(3^40) + log3(3^5 - 1) = 40 + log3(242);
real_x = ceil(x);

另一种获得答案的直观方法是问自己这个问题:

一次称重最多能检查多少个球?

答案是3。原因是,如果你比较三个球中的两个,你要么立即找到不同重量的一个(无论是重的还是轻的),要么你发现它们的重量相等,通过消除过程,导致第三个球的重量不同。

结果,可以将N个球除以3个组加上M的余数组(0<=M<3)。每3人一组施加一个这样的权重,将消除所有球的2/3 rds。这意味着你只剩下一组新的球,你需要从中找到不同重量的球,这组球的数量等于地板(N/3)+M。

通过对这组减少的球应用相同的过程,您可以在一般情况下最多在天花板(log(N)/log(3))步骤中找到不同重量的球。ceiling()语句的原因是,您最终可能会用完3个球组,而剩下的2个球组需要额外的1个权重。(如果最后一组只有一个球,你不必称它来推断它一定是一个不同重量的球。更精确地表述了要求出现在最多楼层(对数(N)/对数(3))+1的权重数;从这里可以简单地观察到,如果对数(N)/对数(3)是整数,则不需要额外的1个权重,从而得到更精确的上限值(对数(N)/对数(3))

根据你的例子,我们不得不推断不同重量的球要么已知较重,要么已知较轻。为了简单起见,我假设它比较重。

首先让我们看看为什么可以在45次称重中做到这一点:对于3n个球,一个可以称n对n,留下n个未移动的球,并减少到n个球。这样做40次,减少到一批(3^45-3^40)/3^40=3^5-1=242个球。那个重球在里面的某个地方。加上一个已知的普通球,你就有243(再次是3的力量),然后再继续5次称重,之后你就有了重球。

接下来让我们看看为什么不能在44次或更少的称重中完成:每一次称重为您提供一条信息,可以将其视为数字0、1或2。0表示“重球在左边”,1表示“重球在右边”,2表示“重球在未移动的批中”。无论对相同数量的球称重多少球,都是这样。因此,任何44次称重的结果都可以看作是44位数字的序列——0、1和2 任何 战略使用44磅。但是你有超过3^44个球,所以你不能保证通过一个实验过程找到正确的球,这个过程只产生3^44个不同的答案。从信息论的角度看,“正确答案”中的信息比44次称重所能产生的信息要多。