欢迎来到人道堂

首页 » 潜能开发 » 逻辑推理 » 正文

城市牛皮癣

作者: | 文章出处:人道堂 | 更新时间:2015-07-13 | 浏览次数:

公路上有2005根电线杆,它们是等距排列的,每两根之间的距离称为一个“杆距”。现在给你2005张“香港老军医”广告,分别贴在每根电线杆上。由于付给你的报酬是按你走过的杆距计算的,请设计一种走法,使得你走过的计费杆距最多,得到的报酬也最多。

    计费杆距计算的规则是:从你任意选定某根电线杆贴上第一张广告算起,至你贴上最后一张广告为止。如果中间有折返点,必须在某根电线杆处折返,折返处的电线杆上要贴广告。

    要求写出N根电线杆时计费杆距的最大值公式,并证明之。

 

(拖动鼠标选择下面空白区域查看答案)

n=0时,y=0,不用贴。n=1时,y=0,白贴,大概没人干。
 
不妨先做一个闭合的线路来考虑这个问题,即贴完最后一根后再回到第一根,则其行程可表示为:
y=|x1-x2|+|x2-x3|+......+|x2004-x2005|+|x2005-x1|
求y的极大值。
 
去掉绝对值后,y=a1-b1+a2-b2+a3-b3+.......a2005-b2005=(a1+a2+.....+a2005)-(b1+b2+......+b2005)
令这2005个点分别为1,2,3,4,......,2005
则a1+a2+a3+.....+a2005最大为2005+2005+2004+2004+2003+......+1004+1004+1003
b1+b2+...+b2005最小为1+1+2+2+3+3+......+1002+1002+1003
于是y的最大值为2005+2005+2004+....+1004+1004+1003-1-1-2-2-......-1002-1002-1003=1003*1002*2=2010012
最后去掉闭合线路中的一条最短的:1003-1002=1
得到答案2010011

(拖动鼠标选择上面空白区域查看答案)

标签:城市,牛皮癣

留言板

全部留言