電子天平該如何選擇合適的砝碼 [砝碼稱重問題]給定架天平，要求用m個砝碼稱出1~n克范圍內的所有物品的重量，問應該如何選擇砝碼 定理： 由m個數構成的由小到排列的數列，設A（k）=∑ a（i）， 其中i從1到k， 則 a（1） = 1且a（j+1） <= 2A（j） +1， j取1,2,..,m-1 （1式） 是該數列作為砝碼序列可稱量范圍內的任意整數重量的充要條件。特 別的，上式取等號時， 該序列是*可能的砝碼序列，并且有a（j） = 3^（j-1）， 對于j=1,2,..,m 推論： 重量為n的物體要分成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搜索就可以了。可以遞歸的搜索求解。具體我就不寫程序了。 終于寫完了，好累呀~~ ———————————————  ———砝碼質量等級表 | 標稱值 | E2等 | F1等 | F2等 | M1等 | | 20kg | 30 | 100 | 300 | 1000 | | 10kg | 16 | 50 | 160 | 500 | | 5kg | 8.0 | 25 | 80 | 250 | | 2kg | 3.0 | 10 | 30 | 100 | | 1kg | 1.6 | 5 | 16 | 50 | | 500g | 0.8 | 2.5 | 8 | 25 | | 200g | 0.3 | 1 | 3.0 | 10 | | 100g | 0.16 | 0.5 | 1.6 | 5 | | 50g | 0.10 | 0.30 | 1.0 | 3.0 | | 20g | 0.08 | 0.25 | 0.8 | 2.5 | | 10g | 0.06 | 0.20 | 0.6 | 2 | | 5g | 0.05 | 0.16 | 0.5 | 1.6 | | 2g | 0.04 | 0.12 | 0.4 | 1.2 | | 1g | 0.03 | 0.10 | 0.3 | 1.0 | | 500mg | 0.025 | 0.08 | 0.25 | 0.8 | | 200mg | 0.020 | 0.06 | 0.20 | 0.6 | | 100mg | 0.016 | 0.05 | 0.16 | 0.5 | | 50mg | 0.012 | 0.04 | 0.12 | 0.4 | | 20mg | 0.010 | 0.03 | 0.10 | 0.3 | | 10mg | 0.008 | 0.025 | 0.08 | 0.25 | | 5mg | 0.006 | 0.020 | 0.06 | 0.20 | | 1mg 2mg | 0.006 | 0.020 | 0.06 | 0.20 | |
