砝碼稱重問題

1、膄【砝碼稱重問題】莀艿曾經(jīng)有人出過這樣一道題：怎樣用四顆砝碼，用天平把直到40 磅為止的各個(gè)整數(shù)磅數(shù)的物體稱出來？法國數(shù)學(xué)家巴舍德梅齊里亞克（Bachet de Meiziriac ）在他的數(shù)學(xué)趣題 （ 1624年）中，提到了這個(gè)問題。這個(gè)問題用二進(jìn)制砝碼是解決不了的，盡管如今的計(jì)算機(jī)都要使用二進(jìn)制。因?yàn)橛?磅、 2 磅、 4 磅、 8 磅四塊砝碼最多只能稱出1+2+4+8=15 磅的物體。很自然我們會(huì)想到二進(jìn)制不行，那么試試三進(jìn)制看看行不行，1+3+9+27=40 磅正好符合我們的要求。雖然最大我們能夠稱出 40 磅的物體來，但是1、 3、 9、27 的各種組合只有 1、 3、 4、9、 1

2、0、12、13、 27、28、30、31、36、37、39、40 磅，其中缺少許多整數(shù)磅。不過我們有一種巧妙的方法，可以解決這個(gè)難題，我們可以把砝碼加在天平上那個(gè)稱東西的盤子上，因此，這塊砝碼不是要加在稱出的重量上面，而是要從中減去的數(shù)。比如5=9-3-1 、 6=9-3 、 7=9+1-3等等。為了達(dá)到這個(gè)目的，這里所用的三進(jìn)制數(shù)碼不是通常的0、 1、 2，而是 -1、 0、 1。不錯(cuò)，在用 3 作為底數(shù)時(shí)，所用數(shù)碼是0、 1、 2，但是 2 可以寫成 3-1，因此可以化成 -1這個(gè)數(shù)字。下面可以看到這么處理的方便之處。為了簡(jiǎn)便，我們把-1 寫成 i，以后只要在三進(jìn)制中碰到 2 這個(gè)數(shù)字，我

3、們就把它改寫成1i （即 3-1=2）例如，三進(jìn)制中的22102 這個(gè)數(shù)，可以用下面的加法表改寫成10i11i 。肅+ 莁 1 肂 i膅肈 1 1i 螂 0芅葿 i 螇 0 i1膃芁 22102=袀1i芅薃蠆1i薈101i（ +10i11i為了稱出14 磅，先將14 化成普通三進(jìn)制112，再改寫成1iii ，方法如下：112=1101i（ +1iii這就是說，我們應(yīng)該把27 這塊砝碼放進(jìn)砝碼盤，而把9、3、1三塊砝碼放進(jìn)稱物盤中： 27-9-3-1=14再看怎樣稱出35 磅來， 35=27+6+2= （ 1022 ）3=110i ，所以應(yīng)該把27、 9 這兩塊砝碼放進(jìn)砝碼盤，而把1 磅這塊砝碼

4、放進(jìn)稱物盤中。這樣我們完全解決了用四塊砝碼稱出40 磅以下所有整數(shù)磅物體的問題。該結(jié)論可以推廣到稱量超過40 磅的物體上去，這時(shí)，我們要再加一塊81 磅的砝碼，最大可稱量：1+3+9+27+81=121 磅顯然，如果有n 塊三進(jìn)制砝碼，則最大可稱量的物品重量為：1+3+32+33+.+3(n-1)=(3n-1)/2磅不過用這種三進(jìn)制的方法還是過于繁瑣，我還是用老一套遞推方法。首先必須有1磅，不然就無法稱量1 磅的物品，所以我們得到了第一塊砝碼：1 磅?，F(xiàn)在1 磅的物品可以稱量了， 再增加一磅， 2 磅怎樣稱量呢？2=1+1，顯然還需要一塊1 磅的砝碼， 但是如果我們要求每塊砝碼都盡量大，那么增

5、加一塊1 磅的砝碼就不符合要求了。因?yàn)槲覀円部梢栽黾右粔K2 磅的砝碼，而能夠直接稱量2 磅的物品；還可以大嗎？增加一塊3 磅的，正好滿足要求： 1=1 ，2=3-1， 3=3 ，4=1+3。我們看到： （ 1，1）；（ 1，2）；（ 1，3）；都可以滿足稱量連續(xù)整數(shù)磅的物品，而其中（1， 3）滿足砝碼盡量大的要求。但是也不能任意大，因?yàn)椋?1，4）不能稱量 2 磅的物品，所以3 磅是可選的第二塊砝碼中最大的一個(gè)，如果不要求盡量大，那么 1， 2，3 都是可選的第二塊砝碼?，F(xiàn)在能稱量的最大重量是1+3=4 磅，大于這個(gè)數(shù)就必須再增加砝碼了，假設(shè)增加一塊x 磅的砝碼，則稱量 5磅 =x- （1+3

6、 ），求出第三塊砝碼 x=5+4=9 磅，現(xiàn)在能稱量從1 到（ 1+3+9） =13 磅的所有連續(xù)磅數(shù)的物品了，稱量 14 磅=x- （ 1+3+9 ）， x=14+13=27 磅。這樣我們得到了4 塊砝碼組（ 1， 3， 9，27）。那么一般情況是怎樣的呢？我們看到，若已經(jīng)知道前幾塊砝碼重量各是a0， a1， .ak-1磅，則下一塊砝碼的重量akk0 1k-1 ），但是也可以ak 1+2（ a0+a1+.+a k-1 ），那么最小不可稱量數(shù) 1+（ a0+a1+.+ak-1 ）就無法稱量了。那么如何確定a0 ，a1， .ak呢？現(xiàn)要求尋找能夠稱量從 1 到 N 磅的砝碼，如果 a 是尋找到的

7、最大一塊砝碼，而N = a + b ，而 b 是已經(jīng)確定好的能夠稱量從1 到 b磅的砝碼重量之和，那么應(yīng)該滿足： a 1+2b =1+2（ N-a）=2N+1-2a ，所以有： a （ 2N+1 ）/3 。如果用取整符號(hào)則有： a = （ 2N+1 ）/3 。這樣確定了 a 之后，對(duì) b 繼續(xù)應(yīng)用如上規(guī)則，即可確定全部砝碼。我們來看幾個(gè)例子，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

8、）。再看， 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）。我們?cè)倏纯碞=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 塊砝碼 .以下無正文僅供個(gè)人用于學(xué)習(xí)、研究；不得用于商業(yè)用途。 , , .For personal use only in study and research; not for commercial use.Nur f r den pers?nlichen f r Studien, F