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

王德貴

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

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

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

二、算法分析

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

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

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

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

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

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

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

三、程序實現

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

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

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

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

3.時間復雜度

循環值雖然不大，但是8重循環，時間復雜度為37×37×37×40×3×3×3×3=164115720。大約10的8次方。這個運算次數在Python運行時間只需要0.5秒。運行結果如下圖。

四、結論

要能夠滿足題意的條件.那么小砝碼磅數之和所表示數的下一個數應當為最大數減去小砝碼磅數之和。因為幾個小磅數囊括了其小磅數和內所有數字才能滿足這個砝碼問題，下一個磅數，小磅數和已經不能滿足，大數也滿足不了，那么就只能用大數減去小磅數和得到，即下一個磅數是y=2*x+l，x為小磅數之和。

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

五、小結

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