德·梅齐里亚克砝码问题的分析与PVthon解法

2021-07-29王德贵

电脑报 2021年27期

关键词：砝码排列组合重物

王德贵

在数学史上，有很多未被证明的猜想和定理，它们也成了著名的数学难题，而其中关于数论的问题有很多，今天我们用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。