砝码称重问题.doc

羈【砝码称重问题】袂袁曾经有人出过这样一道题:怎样用四颗砝码,用天平把直到40磅为止的各个整数磅数的物体称出来? 法国数学家巴舍·德·梅齐里亚克(BachetdeMeiziriac)在他的《数学趣题》(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磅的,正好满足要求:1=1,2=3-1,3=3,4=1+3。我们看到:(1,1);(1,2);(1,3);都可以满足称量连续整数磅的物品,而其中(1,3)满足砝码尽量大的要求。但是也不能任意大,因为(1,4)不能称量2磅的物品,所以3磅是可选的第二块砝码中最大的一个,如果不要求尽量大,那么1,2,3都是可选的第二块砝码。