《砝码称重问题.doc》由会员分享，可在线阅读，更多相关《砝码称重问题.doc（4页珍藏版）》请在三一文库上搜索。
1、膄【砝码称重问题】莀艿曾经有人出过这样一道题：怎样用四颗砝码，用天平把直到40 磅为止的各个整数磅数的物体称出来？法国数学家巴舍·德·梅齐里亚克（Bachet de Meiziriac ）在他的数学趣题 （ 1624年）中，提到了这个问题。这个问题用二进制砝码是解决不了的，尽管如今的计算机都要使用二进制。因为用1磅、 2 磅、 4 磅、 8 磅四块砝码最多只能称出1+2+4+8=15 磅的物体。很自然我们会想到二进制不行，那么试试三进制看看行不行，1+3+9+27=40 磅正好符合我们的要求。虽然最大我们能够称出 40 磅的物体来，但是1、 3、 9、27 的各种组合只有
2、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，以后只要在三进制
3、中碰到 2 这个数字，我们就把它改写成1i （即 3-1=2）例如，三进制中的22102 这个数，可以用下面的加法表改写成10i11i 。肅+ 莁 1 肂 i膅肈 1 1i 螂 0芅葿 i 螇 0 i1膃芁 22102=袀1i芅薃虿1i薈101i（ +10i11i为了称出14 磅，先将14 化成普通三进制112，再改写成1iii ，方法如下：112=1101i（ +1iii这就是说，我们应该把27 这块砝码放进砝码盘，而把9、3、1三块砝码放进称物盘中： 27-9-3-1=14再看怎样称出35 磅来， 35=27+6+2= （ 1022 ）3=110i ，所以应该把27、 9 这两块砝码放进砝
4、码盘，而把1 磅这块砝码放进称物盘中。这样我们完全解决了用四块砝码称出40 磅以下所有整数磅物体的问题。该结论可以推广到称量超过40 磅的物体上去，这时，我们要再加一块81 磅的砝码，最大可称量：1+3+9+27+81=121 磅显然，如果有n 块三进制砝码，则最大可称量的物品重量为：1+3+32+33+.+3(n-1)=(3n-1)/2磅不过用这种三进制的方法还是过于繁琐，我还是用老一套递推方法。首先必须有1磅，不然就无法称量1 磅的物品，所以我们得到了第一块砝码：1 磅。现在1 磅的物品可以称量了， 再增加一磅， 2 磅怎样称量呢？2=1+1，显然还需要一块1 磅的砝码， 但是如果我们要求
5、每块砝码都尽量大，那么增加一块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 都是可选的第二块砝码。现在能称量的最大重量是1+3=4 磅，大于这个数就必须再增加砝码了，假设增加一块x 磅的砝码，则称量
6、 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）。那么一般情况是怎样的呢？我们看到，若已经知道前几块砝码重量各是a0， a1， .ak-1磅，则下一块砝码的重量akk0 1k-1 ），但是也可以ak< 1+2满足公式： a =1+2 （ a +a +.+a（ a0 +a1+.+ak-1 ），可是绝对不能大于，因为如果有ak > 1+2（ a0+a1+.+a k-1 ），那么最
7、小不可称量数 1+（ a0+a1+.+ak-1 ）就无法称量了。那么如何确定a0 ，a1， .ak呢？现要求寻找能够称量从 1 到 N 磅的砝码，如果 a 是寻找到的最大一块砝码，而N = a + b ，而 b 是已经确定好的能够称量从1 到 b磅的砝码重量之和，那么应该满足： 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=1
8、7 ，25-17=8 ， （ 2*8+1 ） /3=5 ， 8-5=3， （ 2*3+1 ） /3=2 ， 3-2=1 ，所以确定出砝码组是（1，2， 5，17，50）。再看， N=67 ，（ 2*67+1 ）/3=45 ，67-45=22 ，（2*22+1 ）/3=15 ，22-15=7 ，（ 2*7+1 ）/3=5 ， 7-5=2， （ 2*2+1 ） /3=1 ，2-1=1 ，所以砝码组为（45， 15， 5， 1， 1）。N=83 ，（ 2*83+1 ）/3=55 ，83-55=28 ，（2*28+1 ）/3=19 ，28-19=9 ，（ 2*9+1 ）/3=6 ，9-6=3， （ 2
9、*3+1 ）/3=2 ，3-2=1 ，所以砝码组为： （ 55， 19， 6， 2，1）。我们再看看N=41 怎样确定砝码组， （ 2*41+1 ） /3=27 ， 41-27=14 ，2*14+1/3=9 ，14-9=5 ， （ 2*5+1 ） /3=3 ，5-3=2 ， 2=1+1，所以砝码组为： （ 27，9， 3，1， 1）。恰好是在40 磅的称量法中再增加一块1 磅的砝码。显然若 3n-1 < 2N+1 3n 则需要 n 块砝码 .以下无正文仅供个人用于学习、研究；不得用于商业用途。 , , .For personal use only in study and research; not for commercial use.Nur f ü r den pers?nlichen fü r Studien, Forschung, zu kommerziellen Zwecken verwendet werden.Pour l 'é tude et la recherche uniquementà des fins personnelles; pasà des fins commerciales.