【砝码称重问题】
--------------------------------------------------------------------------------
发表日期:2004年4月3日已经有300位读者读过此文
曾经有人出过这样一道题:怎样用四颗砝码,用天平把直到40磅为止的各个整数磅数的物体称出来?
法国数学家巴舍·德·梅齐里亚克(Bachet de Meiziriac)在他的《数学趣题》(1624年)中,提到了这个问题。
这个问题用二进制砝码是解决不了的,尽管如今的计算机都要使用二进制。因为用1磅、2磅、4磅、8磅四块砝码最多只能称出1+2+4+8=15磅的物体。很自然我们会想到二进制不行,那么试试三进制看看行不行,1+3+9+27=40磅正好符合我们的要求。虽然最大我们能够称出40磅的物体来,但是 1、3、9、27的各种组合只有1、3、4、9、10、12、13、27、28、30、31、36、37、39、40磅,其中缺少许多整数磅。不过我们有一种巧妙的方法,可以解决这个难题,我们可以把砝码加在天平上那个称东西的盘子上,因此,这块砝码不是要加在称出的重量上面,而是要从中减去的数。比如5=9-3-1、6=9-3、7=9+1-3等等。为了达到这个目的,这里所用的三进制数码不是通常的0、1、2,而是-1、0、1。不错,在用3作为底数时,所用数码是0、1、2,但是2可以写成3-1,因此可以化成-1这个数字。下面可以看到这么处理的方便之处。为了简便,我们把-1写成i,以后只要在三进制中碰到2这个数字,我们就把它改写成1i(即3-1=2)例如,三进制中的22102这个数,可以用下面的加法表改写成10i11i。
+ 1 i
1 1i 0
i 0 i1
22102= 1i
1i
1
0
1i (+
———————
10i11i
为了称出14磅,先将14化成普通三进制112,再改写成1iii,方法如下:
112= 110
1i (+
———————
1iii
这就是说,我们应该把27这块砝码放进砝码盘,而把9、3、1三块砝码放进称物盘中:
27-9-3-1=14
再看怎样称出35磅来,35=27+6+2=(1022)3=110i,所以应该把27、9这两块砝码放进砝码盘,而把1磅这块砝码放进称物盘中。
这样我们完全解决了用四块砝码称出40磅以下所有整数磅物体的问题。
该结论可以推广到称量超过40磅的物体上去,这时,我们要再加一块81磅的砝码,最大可称量:
1+3+9+27+81=121磅
显然,如果有n块三进制砝码,则最大可称量的物品重量为:
1+3+3^2+3^3+...+3^(n-1)=(3^n-1)/2磅
不过用这种三进制的方法还是过于繁琐,我还是用老一套——递推方法。首先必须有1磅,不然就无法称量1磅的物品,所以我们得到了第一块砝码:1磅。现在1磅的物品可以称量了,再增加一磅,2磅怎样称量呢?2=1+1,显然还需要一块1磅的砝码,但是如果我们要求每块砝码都尽量大,那么增加一块1磅的砝码就不符合要求了。因为我们也可以增加一块2磅的砝码,而能够直接称量2磅的物品;还可以大吗?增加一块3磅的,正好满足要求:
【砝码称重问题】 来自淘豆网www.taodocs.com转载请标明出处.