電子天平該如何選擇合適的砝碼

電子天平該如何選擇合適的砝碼

 [砝碼稱重問題]給定一架天平，要求用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搜索就可以了。可以遞歸的搜索求解。具體我就不寫程序了。