砝码称重问题.doc

《砝码称重问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、膄【砝码称重问题】莀艿曾经有人出过这样一道题：怎样用四颗砝码，用天平把直到40磅为止的各个整数磅数的物体称出来？ 　　法国数学家巴舍·德·梅齐里亚克（BachetdeMeiziriac）在他的《数学趣题》（1624年）中，提到了这个问题。 　　这个问题用二进制砝码是解决不了的，尽管如今的计算机都要使用二进制。因为用1磅、2磅、4磅、8磅四块砝码最多只能称出1+2+4+8=15磅的物体。很自然我们会想到二进制不行，那么试试三进制看看行不行，1+3+9+27=40磅正好符合我们的要求。虽然最大我们能够称出40磅的物体来，但

2、是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这个数字。下面可以看到这么

3、处理的方便之处。为了简便，我们把-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这就是说，我们应该

4、把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-

5、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）；都可以满足称量连

6、续整数磅的物品，而其中（1，3）满足砝码尽量大的要求。但是也不能任意大，因为（1，4）不能称量2磅的物品，所以3磅是可选的第二块砝码中最大的一个，如果不要求尽量大，那么1，2，3都是可选的第二块砝码。现在能称量的最大重量是1+3=4磅，大于这个数就必须再增加砝码了，假设增加一块x磅的砝码，则称量5磅=x-（1+3），求出第三块砝码x=5+4=9磅，现在能称量从1到（1+3+9）=13磅的所有连续磅数的物品了，称量14磅=x-（1+3+9），x=14+13=27磅。这样我们得到了4块砝码组（1，3，9，27）。    那

7、么一般情况是怎样的呢？我们看到，若已经知道前几块砝码重量各是a0，a1，...ak-1磅，则下一块砝码的重量ak满足公式：ak=1+2（a0+a1+...+ak-1），但是也可以ak<1+2（a0+a1+...+ak-1），可是绝对不能大于，因为如果有ak>1+2（a0+a1+...+ak-1），那么最小不可称量数1+（a0+a1+...+ak-1）就无法称量了。那么如何确定a0，a1，...ak呢？现要求寻找能够称量从1到N磅的砝码， 如果a是寻找到的最大一块砝码，而N=a+b，而b是已经确定好的能够称量从1到b磅的

8、砝码重量之和，那么应该满足：a≤1+2b=1+2（N-a）=2N+1-2a，所以有：a≤（2N+1）/3。如果用取整符号则有：a=[（2N+1）/3]。这样确定了a之后，对b继续应用如上规则，即可确定全部砝码。    我们来看几个例子，N=75，[（2*75+1）/3]=50，75-50=25，[（2*25+1）/3]=17，25