砝码称重问题

砝码称重问题 曾经有人出过这样一道题:怎样用四颗砝码，用天平把直到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)=110i，所以应该把27、9这两块砝码放进砝3 码盘，而把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都是可选的第二块砝码。现在能称量的最大重量是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)。 那么一般情况是怎样的呢,我们看到，若已经知道前几块砝码重量各是a，a，...a01k-1磅，则下一块砝码的重量 a 满足公式:a = 1+2(a+a+...+a)，但是也可以 a < 1+2kk01k-1k(a+a+...+a)，可是绝对不能大于，因为如果有a > 1+2(a+a+...+a)，那么最小01k-1k01k-1不可称量数1+(a+a+...+a)就无法称量了。那么如何确定a，a，...a 呢,现要求寻01k-101k找能够称量从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]=17，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*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磅的砝码。 n-1n 显然若 3 < 2N+1 ? 3 则需要n块砝码.