8=1+1+2+4

　　9=1+1+2+5

　　10=1+1+3+5

　　11=1+1+3+6

　　12=1+2+3+6

　　13=1+2+3+7

　　14=1+2+4+7

　　15=1+2+4+8

　　對于上面的格羅麗亞太太的79節(jié)金項鏈，79+1=80，80/2=40，所以最大的一節(jié)就是40節(jié)，79-40=39，39+1=40，40/2=20，所以第二大的一節(jié)就是20節(jié)，39-20=19，19+1=20，20/2=10，第三大的一節(jié)是10節(jié)，19-10=9，9+1=10，10/2=5，又找到了一節(jié)是5，9-5=4，4的表示法如上已經(jīng)列出來了：4=1+1+2.最后得到79節(jié)的金項鏈的分割法：1，1，2，5，10，20，40.過去我也碰到過一道類似的題，是23節(jié)金項鏈，也能夠很容易地解決：23+1=24，24/2=12;23-12=11，11=1+1+3+6;所以23的分割法為：1，1，3，6，12.顯然，對于2k-1類型的數(shù)，用這里的辦法與用二進(jìn)制記數(shù)法得出的結(jié)果是一致的.

　　從上面所列出的拆分法可以看出，如果2k=

　　可以用數(shù)學(xué)歸納法很容易地證明這是正確的.那么還有沒有比這更少的分割法呢?可以證明沒有了.從我們的分析方法中可以看出，這是一個構(gòu)造性的推理過程，假如還有比這更少的分割法，那么相當(dāng)于在表達(dá)式n=a0+a1+a2+...+ak.中進(jìn)行了某些組合，比如將a1+a2合并成新的a1，那么原來的有些組合就表示不出來了，例如a0+a2，就沒有辦法組合了.當(dāng)然，一個數(shù)的拆分不是唯一的，前面的23節(jié)金鏈還可以分成1，2，3，6，11.你可以試試，這種分割法照樣能滿足要求.前面的分析中也可以把(n-1)/2留下來作為最大的節(jié)數(shù)，但是這樣分出來的節(jié)數(shù)就不一定都是最少的了，例如把15這樣分割，會得到：1，1，2，4，7.雖然能夠滿足付房費的要求，但是就不是最優(yōu)解了.最后總結(jié)一下，把前面的算法過程公式化可以得到：

　　k-1r-1k-1

　　n=(n+c0)/2+∑{[n-∑cs2s+cr2r]/2r+1}+[n-∑cr2r]/2k

　　r=1s=0r=0

　　其中c0，c1，...ck-1等等是1或是0取決于每一步得出的數(shù)的奇偶性.其實最后一項等于1，這樣可以得出：

　　k-1

　　n-2k=∑cr2r

　　r=0

　　a0=(n+c0)/2

　　i-1

　　ai=[n-∑cs2s+ci2i]/2i+11(i=1，2，3，...k-1)

　　s=0

　　ak=1

　　當(dāng)然，編成計算機(jī)程序還是用遞歸程序比較簡單.這里列出這些公式是為了保留存照。