[砝码称重问题]给定一架天平,要求用m个砝码称出1~n克范围内的所有物品的重量,问应该如何选择砝码
定理: 由m个数构成的由小到大排列的数列{a(1),a(2),...a(m)},设A(k)=∑
a(i), 其中i从1到k, 则
a(1) = 1且a(j+1) <= 2A(j) +1, j取1,2,..,m-1 (1式)
是该数列作为砝码序列可称量{0,1,..,Am}范围内的任意整数重量的充要条件。特
别的,上式取等号时,
该序列是*可能的砝码序列,并且有a(j) = 3^(j-1), 对于j=1,2,..,m
推论: 重量为n的物体要分成m份重量为整数的物体的序列{a(1),a(2),..a(m)},
设M=∑3^(i-1),其中i
从1到m,则有三种情况:
1) M<n, 无解;
2) M=n,有*的解 a(j)=3^(j-1), j=1,2,..m;
3) M>n,可能有多组解,解为满足(1式)并且∑a(i)=n,其中i从1到m,的所有整
数序列。
砝码定理的证明:
(充分性)
用数归法:
当i=1的时候,a(i)=1显然成立;
假设i=k的时候定理充分性成立,即用满足(1)式的前k个砝码可以称量的重量
W(k)为满足0<=W(k)<=A(k)
的所有整数,则i=k+1时,应可以称量W(k+1),应为0<=W(k+1)<=A(k+1)范围内的所
有整数。分段讨论如下:
(a)对于0<=W(k+1)<=A(k),显然可以由前k个砝码称量;
(b)对于A(k)<W(k+1)<=a(k+1), 由假设0<=W(k)<=A(k), 交换左右盘的砝码,可
以产生配合砝码a(k+1)
使用的负砝码为W(k)' 可以是满足-A(k)<=W(k)'<=0的所有整数。与大砝码a(k+1)
一起使用可以得到a
(k+1)+W(k)' ,一定可以称量某段连续范围的所有整数,因为a(k+1) <=2A(k)+1,
所以a(k+1)-A(k) <=
A(k)+1, 因此a(k+1)+W(k)'产生的下限为a(k+1)-A(k),上限为a(k+1),所以可以
称量A(k)<W(k+1)<=a
(k+1)内的所有W(k+1);
(c)对于a(k+1)<=W(k+1)<=A(k+1),与(b)同理可以得到称量的上下限分别为:
a(k+1)+A(k) = A(k+1)和a
(k+1);
因此当i=k+1的时候定理充分性也成立,由数归法知定理充分性成立。
(必要性)
i=1时,显然必须有总量为1的砝码;
i>1时,反证之,如果存在某个K,使得(1)不成立,即2A(k)+1<a(k+1),则重量
A(k)+1既不能用前面的
k-1个砝码称重,又因为a(k+1)-A(k)>A(k)+1而不能用a(k+1)配合着称重。所以矛
盾,因此必要性成立。
推论也可以用数归法简单的证明,这里我就不证了,打字太累了:)
根据以上的定理和推论,可以很容易的求出对于重量为任意的n的物体,用m个砝码
可以称出来的砝码的方
案。当n=∑3^(i-1), i从1到m的时候,有*解a(i)=3^(i-1),可以改写成
a(i)=2(∑aj)+1,其中j从1
到i-1,一个循环就直接输出了;当n>∑3^(i-1)的时候无解;当n<∑3^(i-1)的时
候只要根据式(1)并保
证∑a(i)=n搜索就可以了。可以递归的搜索求解。具体我就不写程序了。