分类:其它JS程序

小球称重问题:用天平称量几次才能找到有问题的球?

在n个外观完全相同的小球中,有一个与其它球重量不同。如何只用一架天平找到这个球并判断它比其它球轻还是重?最少需要称几次?

这是一个流传极广的经典问题,在网上随便一搜就会发现无数人都提出了自己的见解和算法并争论不休。最常见的是12个小球,至于更多球的计算,就不是人力能及的了。

实际上,这个问题确实是有准确答案的:n次称量最多可以在个球中找到不同的球,并判断它的轻重。
理论证明可参考The Problem of the Pennies, F. J. Dyson, The Mathematical Gazette , Vol. 30, No. 291 (Oct., 1946), pp. 231-234。
不过这里不打算讲那么多理论,而是直接演示怎么称量并找到这个小球。

算法十分精巧,我尽可能简单地描述了一下。如果还是觉得太抽象,没关系,直接点击这里或者拉到下面看演示就可以了。 [阅读全文]

5+