王德贵

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