断金链难题

    一位来自阿肯色州的年轻太太格罗丽亚,正在加利福尼亚州旅行.她想在旅馆租用一个房间,租期一周.办事员此时正心绪不佳.办事员:"房费每天20元,要付现钱.格罗丽亚:"很抱歉,先生,我没带现钱.但是我有一根金链,共7节,每节都值20元以上.办事员:"好吧,把金链给我."     格罗丽亚:"现在不能给你.我得请珠宝匠把金链割断,每天给你一节,等到周末我有了现钱再把金链赎回.办事员终于同意了,但格罗丽亚必须决定如何断开金链的方法.格罗丽亚:"我该三思而行,因为珠宝匠是按照他所切割和以后重新连接的节数来索价的.格罗丽亚想了一下,悟到她不必把每一节都割断,因为她可以把一段段金链换进换出,以这种方式来付房费.当她算出需要请珠宝匠割断的节数时,她几乎不能自信.你想一想需要割开多少节?

  只需要割开一节.这一节应是从一端数起的第三节.把金链断开成1节,2节,4节这样三段后就能以换进换出的方式每天付给办事员一节作为房费.
  啊哈!领悟到下列两点才能解题.第一,至少需要有1节,2节,4节这样三段(即其节数成二重级数的一些段),这样才能以各种不同的组合方式组成1节,2节,3节,4节,5节,6节和7节.我们在药品混乱问题中已经知道,这就是作为二进制记数法基础的幂级数.

  第二,只需要割开一节就可以把金链分成符合要求的三段.关于这个问题,若把金链的长度增加,则可以想出一些新的问题.例如,假设格罗丽亚有一根63节的金链,她想把金链割开,以上面那种方式来付63天的房费(价格不变).要达到此种目的只需要割开三节.你想出来了吗?你能否根据金链的不同长度设计一个通用的解题程序,要求分割开的节数为最少?

  有一个有趣的变相问题:若所经手的 n 节首尾相连的闭合回路,例如说格罗丽亚有一串金项链,由79节相连而成,若每天房费为一节,试问最少需要分割开几节才能支付79天房费?

  这些问题使我们想到了二进制记数法.比如格罗丽亚的63节金项链如何分割?将63化成二进制表示:等于"111111"即63=1+2+4+8+16+32但是要把其中的2分成两个1，因为在4、8、16、32之间有三个间隔，这条金链子被分割成4段，也就从那三个间隔处割开了三节，所以63应该分成1、1、1、4、8、16、32。对于其他任意类型的数,却不能奏效,比如对于19节金项链,19的二进制记数法表示为"10011".即19=1+2+0+0+16,这样从1到3都能表示,可是从4到15都没法表示了。可以这样:你不是要求节数最少吗?假设 n=a+b 其中 a 是已经找到的最大的那一节数,b 是比 n 小的已经解决了的金链问题,由于 b 已经解决,因此 b 的拆分能够表示从1,2,3,...b-1,b 的所有金链节数,而再大一些的数就不能够表示了,比如 b+1,所以必须要 a 参加进来,如果 n 是奇数,可令 a=b+1,这样 n=2b+1,所以 b=(n-1)/2,a=(n+1)/2,这样就找到了最大的一节的节数 a ,然后对 b=(n-1)/2继续应用如上的办法,即可解决问题.如果 n 是偶数,可令 a=b ,这样虽然 a 本身不能表示出 b+1,但是可以从 b 的拆分中拿出一个1来(这个1是必须存在的,因为要表示从1,2,3,...b-1,b的所有数)与 a 组成 a+1 也就是 b+1.所以 n=a+b=2a=2b,a=b=n/2.这样也找到了 n 为偶数时最大的一节金链的节数.对于 b 继续如上的过程,就可以找到全部应该断开的金链节数,我算出了从1到16的所有拆分如下:
                                          1=1
                                          2=1+1
                                          3=1+1+1
                                          4=1+1+2
                                          5=1+1+3
                                          6=1+2+3
                                          7=1+2+4
                                          8=1+1+2+4
                                          9=1+1+2+5
                                          10=1+1+3+5
                                          11=1+1+3+6
                                          12=1+1+2+3+5
                                          13=1+1+2+3+6
                                          14=1+1+1+4+7
                                          15=1+1+1+4+8
                                          16=1+1+2+4+8
    上面的分成偶数节数是这样分的，比如8=1+1+2+4，是将第三节、第四节割开。对于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.最后得到19节的金链子的分割法:1,1,2,5,10.过去我也碰到过一道类似的题,是23节金链子,也能够很容易地解决:23+1=24,24/2=12;23-12=11,11=1+1+3+6;所以23的分割法为:1,1,3,6,12.显然,对于2^k-1类型的数,用这里的办法与用二进制记数法得出的结果是一致的.当然,一个数的拆分不是唯一的,例如把15这样分割,会得到:1,1,2,4,7.也能够满足付房费的要求.

    上面提到的都是对于金链子的分割问题，对于金项链这样闭环的情况，要增加一节，只要把第一个不为1的数分出去一个1即可达到目的。如上面提到的79节金项链,(79+1)/2=40,79-40=39,(39+1)/2=20,39-20=19,19=1+1+2+5+10，所以我们得到1，1，2，5，10，20，40，但是在2，5，10，20，40之间有4个空隙，要将2分成1+1，这样也满足闭环的分割要求了，最后得到1，1，1，1，5，10，20，40。