|
割手链
|
|
a．格罗莉亚是来自阿肯色的一位年轻女士，正在加利福尼亚走访，她想在旅店租一间房间，准备住7天。 |
|
|
b．店员：房间20美元一天，必须付现金。
格罗莉亚：对不起，先生，我一点儿现金没有，但我有一个金手链，七节中每节价值超过20美元。 |
|
|
c．店员：好吧，把手链给我。
格罗莉亚：不，现在不行，我找个手饰匠把手链割开，每天我给你一节，最后有钱时我再把手链赎回来。 |
|
|
d．店员最后同意了，现在该格罗莉亚决定怎样割手链了，她反而为难了。 |
|
|
e．格罗莉亚：我一定得小心，手饰匠每多割一节，每多接一节都要手工钱。 |
|
|
f．想了一会，格罗莉亚发现她不必每节都割，因为地可以来回兑换。当她想出能割几节时，她简直难以相信。你算出割几节了吗? |
|
|
g．只需割一节，它应是从一端数第三节，把手链分成三段，各为1、2、4节，这足够通过来回兑换使店员每天收到一节。 |
难解的链
解决这个问题需要两个重要的观点。首先按不同方法形成1、2、3、4、5、6、7节的链中，最小集合的链是1、2、4节的链，即形成等比数列，正如我们在上一个问题中知道的这是作为二进制基础的幂系列。
第二是认识到仅割一次就能把手链分成所需的三段。
这个问题也可推广到较长的链中。比如假设格罗莉亚有一条63节的金链，她想像手链一样割开使用，一天用一节。割三个环就能达到目的。你知道怎么办吗?对于任意长度的链你能想出一般方法来解决问题吗?
这个问题的一个有趣的变化就是几节链首尾相连作为一个封闭的环。例如，假设格罗莉亚有一条项链，是一条79节金环的封闭链，一环花一天，要割几环就可以花79天。
来源:本站原创 | 
