主题：巧断金链
＆佑慧妹妹＆
[专家分：660] 发布于 2007-05-12 15:43:00
问题描述：一位聪明的商人走南闯北跑生意，有一天他来到一个小客栈投宿，准备住6天，由于刚支付一笔货物的订金，商人花光了所有的现银，身边只剩下一条他喜爱的金链，共6节，投宿客栈一天的费用恰好值一节金链。店老板有一条古怪的规定：当天的费用必须当天结清，不许拖欠也不许预支。如果商人将6节金链全部割断，每天给店主一节就可以满足这条古怪的规定，但这样6节金链都被损坏了。于是商人想了一个办法，将金链分成长度分别为1、2、3节的3段，既满足了店主的要求，也使金链受损最小。下图是商人聪明的分法：
你的任务是写一个程序，假定商人有一根N节的金链，需投宿N天，计算最少将金链分割成几段，才能满足店主古怪的要求。
输入：输入文件为G.in，只有一行一个正整数N（1≤N≤10000）。
输出：输出文件为G.out，只有一行，输出应该切成的段数。
输入输出样例：
输入样例 输出样例
6 3
回复列表 （共10个回复）
沙发
＆佑慧妹妹＆ [专家分：660] 发布于 2007-05-12 15:44:00
给出算法
板凳
moz [专家分：37620] 发布于 2007-05-12 16:16:00
6节的金链只要把中间的那节打开，就能分成1,2,3三段各1,2,3节的金链了，
第二天，商人拿着两节金链，付第二天的房费，并要求房东找零的时候，
房东说：昨天那节金链送二奶去了，没得找……那可怎么办……？
反正都是当钱付给人家的，管它损坏不损坏的？
你要是说金链很难弄断，怎样才能最省力气那还说得过去。
（金链那么软，随便一扭都断了。）
现在出题的人脑袋都不知道哪去了。
3 楼
＆佑慧妹妹＆ [专家分：660] 发布于 2007-05-12 16:19:00
moz大哥，别开玩笑啦~~（其实还在笑），损坏金链最小，应该怎么想呢？
4 楼
boolint [专家分：240] 发布于 2007-05-12 17:20:00
应该挺简单的嘛
商人住N天，金链有N节
商人在第i天使用的金链的节数，是前i-1天使用的金链节数之和。
只需满足1+2+3+6+12++24+...=N ，其中加数的个数就是要分成的断数。
5 楼
Matodied [专家分：7560] 发布于 2007-05-12 17:29:00
算法:
(1)假设第1段是1个,第2段是2个,第3段是4个……第D段是2^(D-1)个,此时剩下的金链节数小于2^D,这个时候已经不能在截一段了,于是把它单独分成一段.
CLS
INPUT n
i = 1
DO
k = k + 1: n = n - i: i = i * 2
LOOP UNTIL n < i
IF n = 0 THEN PRINT k ELSE PRINT k + 1
END
也要加分！！！
6 楼
boolint [专家分：240] 发布于 2007-05-12 17:31:00
哦，还有一点，也非常重要
我上面讲的 N 是指为偶数时
下面讲一下 N 为奇数
此时满足1+2+3+6+12++24+...=N-1 就可以了，这样截的话，最后会剩下最后一节金链，所以N为奇数时，有两段 1 节的金链
OK.
7 楼
moz [专家分：37620] 发布于 2007-05-12 17:54:00
我没戴过金链，不知道一节是怎么个概念。
是不是六个环，把中间的一个环打开了，就能拆成三段的这个意思？
456楼的想法的方向大致正确
不过你可以想想这样子是不是更好？
1,2,4,8,16,32,64,128,.....
8 楼
ninke [专家分：60] 发布于 2007-05-16 18:45:00
我是来赞一下6楼的签名的，不过别带坏小孩子哦。
9 楼
冷石_jasv [专家分：1570] 发布于 2007-05-20 08:36:00
一般来说：
魔由心生....
10 楼
staa [专家分：3690] 发布于 2007-05-21 11:23:00
我支持7楼的想法,这是一个天然的翻倍数列,前N位数的和再加1,正好等于第N+1位的数值.
我来回复
您所在位置：