德·梅齊里亞克砝碼問題的分析與PVthon解法

王德貴

在數(shù)學(xué)史上，有很多未被證明的猜想和定理，它們也成了著名的數(shù)學(xué)難題，而其中關(guān)于數(shù)論的問題有很多，今天我們用Python來求解德·梅齊里亞克的砝碼問題。以后還將不定期地發(fā)布類似問題，歡迎關(guān)注。

一、德·梅齊里亞克的砝碼問題

一位商人有一個(gè)40磅的砝碼，由于跌落在地而碎成4塊。后來，稱得每塊碎片的重量都是整磅數(shù)，而且可以用這4塊來稱從1至40磅之間的任意整數(shù)磅的重物。問這4塊砝碼碎片各重多少？

二、算法分析

解這個(gè)問題挺有意思的，不需要什么高深的數(shù)學(xué)知識又很好玩。首先我們來參照一下人民幣的幣值。我們的分幣有1、2、5三種幣值，兩兩可以組成1到8之間的若干值，同樣，我們在這道砝碼問題中第一個(gè)要考慮的因素就是排列組合值。1，2，1+2，5，1+5，2+5，1+2+5。

此外，天平稱重的另一個(gè)特性就是，砝碼可以放在左右任意一個(gè)托盤中，所以我們就得到了這個(gè)問題的第二個(gè)特質(zhì)：排列組合得出的結(jié)果可以取加法，還可以取減法。這樣，在上面列出的數(shù)字的基礎(chǔ)上，我們又得到了2-1，5-1，5-2，5-1-2（就像買東西找零錢一樣）。我們發(fā)現(xiàn)這些新的值和上面的值有重合，也就是有冗余值，我們的優(yōu)化過程就是要消除這些冗余值。現(xiàn)在我們得到了兩個(gè)數(shù)學(xué)概念：排列組合和加減法。

根據(jù)題意，分析時(shí)優(yōu)先考慮極限情況，砝碼的磅數(shù)最小的3個(gè)數(shù)是1、1、1，那剩下的砝碼磅數(shù)就是37。因而砝碼重量范圍在Python中用（1。38）表示。但是各種組合形式不明確，對于計(jì)算機(jī)來說采用枚舉算法比較簡單。

1.由于天平可以兩邊放置砝碼，因而砝碼就有3種情況，放在左邊、不放、放在右邊。4個(gè)砝碼位置的參數(shù)用ab，c，d表示，每個(gè)值都設(shè)定為一1，0，1。一1為左邊表示減去值，在Python中用（一1。2）表示。

2.設(shè)定p，q，r為三個(gè)砝碼磅數(shù)，那么第四個(gè)砝碼就是（40-p-q-r），假定p不小于q，q不小于r，r不小于40-p-q-r。這樣可以有效分割總數(shù)40磅，縮小計(jì)算范圍，也避免重復(fù)數(shù)據(jù)。

3.用循環(huán)來判斷1到40磅用什么樣的組合表示。不同組合方式用x==a。p+b*q+c‘r+d‘（40-p-q-r）表示，并且x是從1到40。

4.最后利用集合去重，如果滿足x的值正好是1-40的40個(gè)整數(shù)值，那就可以得到所求的磅值了。

三、程序?qū)崿F(xiàn)

根據(jù)前面的分析，寫出Python程序。代碼如圖：

1.p、q、r三重for循環(huán)，先確定在1-37整數(shù)范圍，并且滿足條件p<=q<=r。

定義空集合XX。xx=set（）。

2然后是四個(gè)砝碼的三種狀態(tài)組合的4重循環(huán)，如果滿足r<40-p-q-r，那么在1-40的循環(huán)中，將滿足x==a*p+b*q+c*r+d*（40-p-q-r）的x值添加到集合xx中，如果XX的長度是40，那就說明1-40的所有值均能組合出來，即輸出這4個(gè)值。

3.時(shí)間復(fù)雜度

循環(huán)值雖然不大，但是8重循環(huán)，時(shí)間復(fù)雜度為37×37×37×40×3×3×3×3=164115720。大約10的8次方。這個(gè)運(yùn)算次數(shù)在Python運(yùn)行時(shí)間只需要0.5秒。運(yùn)行結(jié)果如下圖。

四、結(jié)論

要能夠滿足題意的條件.那么小砝碼磅數(shù)之和所表示數(shù)的下一個(gè)數(shù)應(yīng)當(dāng)為最大數(shù)減去小砝碼磅數(shù)之和。因?yàn)閹讉€(gè)小磅數(shù)囊括了其小磅數(shù)和內(nèi)所有數(shù)字才能滿足這個(gè)砝碼問題，下一個(gè)磅數(shù)，小磅數(shù)和已經(jīng)不能滿足，大數(shù)也滿足不了，那么就只能用大數(shù)減去小磅數(shù)和得到，即下一個(gè)磅數(shù)是y=2*x+l，x為小磅數(shù)之和。

法國數(shù)學(xué)家G_B.德·梅齊里亞克（1581～1638年）在他的著作中解答了這題（因此也稱這個(gè)問題是德·梅齊里亞克的砝碼問題）。為了使兩個(gè)砝碼A與B能稱出最多種重量，必須是1磅和3磅，因?yàn)橛盟鼈兡芊Q出1、2（=3-1）、3（=2*1+1）、4（=3+1）磅的重物。如選第三塊砝碼c，則它的重量為2x（1+3）+1=9磅，則用它們可稱出1至9+4=13磅間的所有整數(shù)磅重物。最后選第四塊砝碼D，使它重量為2x13+1=27磅，那么用這四塊砝碼能稱出從1至27+13=40磅的重物。因此，這四塊砝碼的重量分別為1、3、9、27磅，根據(jù)這個(gè)理論之后的數(shù)字則是81。243。

五、小結(jié)

學(xué)習(xí)編程不能只要讓學(xué)生做出多么好的程序，而是讓學(xué)生在學(xué)習(xí)中，嘗試解決一些問題，掌握分析問題、解決問題的方法，提高解決問題的能力，并且知道獨(dú)立思考問題和團(tuán)結(jié)協(xié)作的重要作用。