|
|
一位来自阿肯色州的年轻太太格罗丽亚，正在加利福尼亚州旅行.她想在旅馆租用一个房间，租期一周.办事员此时正心绪不佳。办事员："房费每天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只要将从第二节开始的两节割开，再将从第八节开始的八节割下来，和从第32节开始的32节割下来即可，这样就有了从1，2，3，4，5，6，直到63的所有节数.一般地，若有n节金链，n是形如2k-1类型的数，将n化成二进制表示，再将所有"1"的位置所代表的2的幂的数相间隔地割开即可达到目的.但是对于其他任意类型的数，却不能奏效，比如对于格罗丽亚的79节金项链，79的二进制记数法表示为"1001111".即79=1+2+4+8+0+0+64，这样从1到15都能表示，可是从16到63都没法表示，我把这个问题做到这里，也一时糊涂起来，但这个问题毕竟不是很复杂，咱们也学一学闵科夫斯基在课堂上口出狂言要解决四色问题的劲头，摸索着来解决一把.咱们可以这样：你不是要求节数最少吗?假设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到15的所有拆分如下：
1=1
2=1+1
3=1+2
4=1+1+2
5=1+1+3
6=1+2+3
7=1+2+4共2页，当前第1页12 |
|
发表于 2021-2-12 11:01:13
