称球问题(zt)

时间:2021-10-29 01:16:03

下面说的这个问题可能大家都看到过,它是这么描述的:

  现在有n(n>=2)个球,n个球外观一模一样,但是重量有区别,其中有且仅有一个球的重量比其它n-1个球要重,现在有一个天平,天平是完好无损的,问最少需要称多少次才能确定哪个球的重量较重?

  初一看这个问题,感觉有点复杂,不知道从何入手。一般情况下,解决类似的问题需要简化问题,然后从中发现规律,从而解决整个问题。可以先假设有2个球,那么称一次就可以知道哪个球重;当有3个球时,也可以通过一次称量就可以确定哪个球重,因为假如放在天平上的球一样重,那么剩下的那个球必定是重球,否则天平重的那端就是重球;当有4个球时,一次称重时无法确定的。。即当球的个数大于3时,是无通过一次称重确定的。下面来分析大于3的情况:

  4个球时,可以称2次确定,分为2组(2,2),先取2个球,天平一端一个,重的那端为重球;若天平平衡,称剩下的一组即可;

  5个球时,也可以2次确定,分为2组(2,3),先取2个球,天平一端一个,重的那端为重球;若天平平衡,剩下的3个球一次称重就可以确定;

  6个球时,也可以两次确定,分为2组(3,3),天平每端放3个球,然后再对重的那端的3个球进行称重;

  7个球时,也可以两次确定,分为3组(2,2,3),先在天平每端放2个球,然后对重的那端再称重;若天平平衡,剩下的3个球一次称重;

  8个球时,也可以2次确定,分为(3,3,2),道理同上;

  9个球时,也可以2次确定,分为(3,3,3),道理同上;

  。。。。

  显然,当有27个球时,可以3次确定,分为(9,9,9),先确定重的那个球在哪9个球里,然后再确定重的那个球在哪3个球里,然后再需1次称量即可。

  从上面的分析可以,发现要想最少次数的称量,必须把球分组,并且组数不大于3,而且一次称重最多能从3个球中确定哪个球中,2次称重最多可以从9个球中确定哪个球重,3次称重最多可以从27个球中确定哪个球重。。m次称重最多可以从3^m个球中确定哪个球重。

  因此,当有n个球时,显然最少需要n^(1/3)次才能确定,这里需要特别说明一下,当n^(1/3)为整数时,最少需要n^(1/3)次;否则最少需要[n^(1/3)]+1次。