+3+6
13=1+2+3+7
14=1+2+4+7
15=1+2+4+8
对于上面的格罗丽亚太太的79节金项链，79+1=80，80/2=40，所以最大的一节就是40节，79-40=39，39+1=40，40/2=20，所以第二大的一节就是20节，39-20=19，19+1=20，20/2=10，第三大的一节是10节，19-10=9，9+1=10，10/2=5，又找到了一节是5，9-5=4，4的表示法如上已经列出来了：4=1+1+2.最后得到79节的金项链的分割法：1，1，2，5，10，20，40.过去我也碰到过一道类似的题，是23节金项链，也能够很容易地解决：23+1=24，24/2=12;23-12=11，11=1+1+3+6;所以23的分割法为：1，1，3，6，12.显然，对于2k-1类型的数，用这里的办法与用二进制记数法得出的结果是一致的.
从上面所列出的拆分法可以看出，如果2k=<N<P>
可以用数学归纳法很容易地证明这是正确的.那么还有没有比这更少的分割法呢?可以证明没有了.从我们的分析方法中可以看出，这是一个构造性的推理过程，假如还有比这更少的分割法，那么相当于在表达式n=a0+a1+a2+...+ak.中进行了某些组合，比如将a1+a2合并成新的a1，那么原来的有些组合就表示不出来了，例如a0+a2，就没有办法组合了.当然，一个数的拆分不是唯一的，前面的23节金链还可以分成1，2，3，6，11.你可以试试，这种分割法照样能满足要求.前面的分析中也可以把(n-1)/2留下来作为最大的节数，但是这样分出来的节数就不一定都是最少的了，例如把15这样分割，会得到：1，1，2，4，7.虽然能够满足付房费的要求，但是就不是最优解了.最后总结一下，把前面的算法过程公式化可以得到：
当然，编成计算机程序还是用递归程序比较简单.这里列出这些公式是为了保留存照。
上一页 [1] [2]
