论文摘要:本文以递归的方法解决历史上著名的德�6�1梅齐里克砝码问题,并加以推广阐述了一种特殊的进制数方式,对此问题作出了一个普遍解:任意给定一个自然数,能够以最少的个数的项保证其和为给定数而又能遍历1到此数间的任意整数。关键词 :进制数 ,遍历,基底,状态值; 一. 问题介绍一位商人有一个40磅重的砝码,由于跌落在地而碎成4块,后来称得每块碎片的重量都是整磅数,而且可以用这4块来称从1至40磅之间的任意整磅数的重物,问这4块砝码碎片各是多少。 摘自《100个著名初等数学问题》二. 问题解决考虑这样一个用法码称重物的问题,实际上是通过在天平两端放不同砝码使各砝码值相加减得到目的值。用递归的方法能很好的解决:设前i块碎片的总质量为 ,由这 块能够称出1~ 之间所有整磅数,那么第 +1块碎片则为2 +1,。它依次减去前 块得到的各个磅数就能得到( +1)~(2 +1),它依次加上前 块得到的各个磅数就能得到(2 + 2)~(3 +1)2 +1 — = +1 2 +1 + = 3 +12 +1 — ( —1) = +2 2 +1 + ( —1) = 3 2 +1 — ( —2) = +3 2 +1 + ( —2) = 3 —1… … … … … … 2 +1 — 1 = 2 2 +1 + 1 = 2 + 2 2 +1自己当然能够称出来; 所以由这 +1块碎片能称出1~(3 +1)所有的整质量。设第 块碎片重为 ,则有: =2 + 1; =2 1 +1; 两式相减得 =3 ; =1,故各碎片的磅数分别为1,3,9,27.满足和为40的要求。答案补充 三、考虑任给一个数分成特定数目的各值,使之能遍历1到此整数 A. 改变特定碎片的磅数那么照样能称出1到总磅数的所有整数值。 如果把总量为42的重物破碎成6块,此6块能称出1到42磅所有重物,它们可以是 1,1,4,4 ,16,16 由前面特殊进制数可以得到1,4,16与0, 1,2相组合能取到2(1 + 4 + 16 )。 B. 回到前面解题之初。 的取值不止有一种可能,若 ≦2 + 1, ① ≦ ,故由前 块能遍历1到 ,而 加上1,2,3,等就能得到 +1, +2, +3, +4,…, + 。于是能够从1取到 + 。② ﹤ ≦2 + 1, — ≦ + 1,由前 块能遍历1到 — —( —1)= — +1 —( —2)= — +2;… … —(0) = + 1, +2,… … + 故这 块碎片能取到1~ + 所有磅数。答案补充 四.最少块数碎片完成遍历。任何一整数在分成各项,其组合能遍历1至此数的所有值,那么其中以3进制即以 做为基底,与状态值的线性组合能够做到项数最少且满足题意。同时最后一项即零头可以不为3的各次幂。①在各种进制中,3进制是随着项数增多,它们的和增多最块的一个。②在各种其它情形中,要保证遍历中的每一个数都只用其中一种方式组合。否则构造组合的方式就会有重合。例如42可以分为: 1,3,6,27,2 也可以分为 1,1,4,4,16,16。五.任意给定数的最少项数分法1,按3进制数将给定数的各项依次写出,直到“零头“不是3的幂为止。这时项数就是该数最小的分解项数。2,利用 三 中的结论,我们可以不受K次幂数的限制,可以在写出每一 的值,只要保证 ≦2 + 1。各项数值丰富起来。还举42的例子①三进制为各基底。1 + 3 + + +… + = 和依次是1 4 13 40 …留下零头2,故最少遍历分解项数是5分解方式:1 ,3 ,9 ,27 ,2 ②.1,2,7,21,111,2,7,20,121,2,6,18,15