塌先生2005系列问题14 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	塌鼻子先生

组别	校尉
级别	奋威校尉
功绩	31
帖子	120
编号	41049
注册	2005-6-15

#1

发表于 2005-7-7 15:40 资料文集短消息只看该作者

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

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

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	大到暴雨


	历城侯中大夫 ★

组别	翰林学士
级别	安北将军
好贴	1
功绩	354
帖子	2643
编号	31833
注册	2005-2-3

#2

发表于 2005-7-7 16:55 资料文集短消息只看该作者

-->1003-->1-->1004-->2-->1005-->........................1001-->2004-->1002-->2005

唉！老板赔死，暴雨累死

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	塌鼻子先生

组别	校尉
级别	奋威校尉
功绩	31
帖子	120
编号	41049
注册	2005-6-15

#3

发表于 2005-7-7 19:18 资料文集短消息只看该作者

回大到暴雨君：

1）不对。你给出的方法并不是计费杆距的最大值。完全可能走出更多的杆距来。
2）本题要求算出计费杆距最大值的具体数。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

#4

发表于 2005-7-8 10:29 资料文集短消息只看该作者

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

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

答：暂时枚举几种想到的方法，各计算一下，取一个大数：
方法一：从1杆走起，走到底(2005)，回头，再走到底(2)，来回：
1->2005->2->2004->3->2003->...->1001->1005->1002->1004->1003
杆距和为：
2004+2003+2002+...+2+1=2004*2005/2=2009010

方法二：从1杆走起，走到1004，回头，再走到底(2)，来回：
1->1004->2->1005->3->1006->...->1001->2004->1002->2005->1003
柑橘和为：
1003+1002+1003+...+1003+1002=(1003+1002)*1002=2009010
(居然完全一样耶)

第二种方法应该和“大到暴雨”一样吧，暂时就想到两种，看来是不对了，我继续想想。

[广告] 《精忠报国岳飞传完整版》火热发布


	塌鼻子先生

组别	校尉
级别	奋威校尉
功绩	31
帖子	120
编号	41049
注册	2005-6-15

#5

发表于 2005-7-8 10:44 资料文集短消息只看该作者

很容易知道这两种方法不对。

当N=5时，按方法一：1-5-2-4-3走有10段，按方法二：1-4-2-5-3走也是10段。但是按2-5-1-4-3走则有11段。当然我没有说N=5时11段是最大值。

[广告] 《精忠报国岳飞传完整版》火热发布


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

#6

发表于 2005-7-8 11:53 资料文集短消息只看该作者

对喔，奇怪，我再想想，另外看看我的13题对了没？

[广告] 真诚支持说岳，携手共创辉煌


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

#7

发表于 2005-7-8 16:31 资料主页文集短消息只看该作者

从边到中的方法
n=4时 2413 f(4)=2+3+2=7应该是最多
把电线杆编号以后可以形成一个排列相邻两数字之差依次求和就得到杆距总和
n=5 24153 f(5)=11

1..5这几个数字组成一个图对所有结点一次遍历形成一条路径线段的权值是端点数字的差求权值最大的一条路经

线段按权值由大到小排列(相差为1) 15 (14 25) (13 24 35) (12 23 34 45)
选择15 14 52 最后从2和4任一出发到3

类似地 1--2005 1--2004 2005-2 2004--3 2--2003...1001--1004 1005--1002 1002--1003(或1004--1003)每选择一条线段访问结点增加一个共有2004条线段权值分别为2004 (2003,2003) (2001,2001) (1999,1999)...(3,3) 1

相加得2005+(3+2003)*1001=2010011

[广告] 真诚支持说岳，携手共创辉煌


	loranrowe

组别	士兵
级别	奋威校尉
好贴	1
功绩	6
帖子	143
编号	17767
注册	2004-9-16

#8

发表于 2005-7-8 17:55 资料短消息只看该作者

这还是个贪婪算法，虽然看起来好了很多，不知道是不是最优解
这个问题用动态规划解是肯定没问题的
不过手工做很繁琐，一定要写个程序的说
或者用字典序列发生算法生成1~2500的字典序列来穷举
同样要写程序
目前想到的可以解决问题的办法
继续思考更好的方法中

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	sky_force (海阔天空)

组别	士兵
级别	护军
功绩	5
帖子	469
编号	22095
注册	2004-11-4

#9

发表于 2005-7-8 19:19 资料个人空间短消息只看该作者

QUOTE:

原帖由loranrowe于2005-07-08, 17:55:13发表
这还是个贪婪算法，虽然看起来好了很多，不知道是不是最优解
这个问题用动态规划解是肯定没问题的
不过手工做很繁琐，一定要写个程序的说
或者用字典序列发生算法生成1~2500的字典序列来穷举
同样要写程序
目前想到的可以解决问题的办法
继续思考更好的方法中

你把状态转移表达式列好再闪人好不好啊

[广告] 《精忠报国岳飞传完整版》火热发布


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

#10

发表于 2005-7-9 11:33 资料文集短消息只看该作者

QUOTE:

原帖由青木风亮于2005-07-08, 16:31:52发表
…………

老版主又回来了？
好像才回来了一两天吧，还是多来射虎坐坐啊^_^

[广告] 真诚支持说岳，携手共创辉煌


	重阳


	高阳侯光禄大夫

组别	翰林学士
级别	前将军
好贴	2
功绩	585
帖子	1775
编号	50
注册	2003-8-21

#11

发表于 2005-7-9 11:42 资料主页文集短消息只看该作者

青木

这个题还真不是一般的难，想了两天，还是没一点头绪。晕了，还是各位计算机专业的来解决吧。

悬赏，能用简明方法给出答案并证明的500通宝。

[广告] 真诚支持说岳，携手共创辉煌


	英布之勇

组别	士兵
级别	讨逆将军
功绩	6
帖子	630
编号	6578
注册	2004-4-7

#12

发表于 2005-7-11 09:51 资料短消息只看该作者

以某根杆子N为参照物，假设每次贴广告都经过这杆子……（先不管能否实现）
那么总行程：
|2005-N|·2+|2004-N|·2+......|1-N|·2，这个算式很容易算得N=1003时候总行程最长，为2010012

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	英布之勇

组别	士兵
级别	讨逆将军
功绩	6
帖子	630
编号	6578
注册	2004-4-7

#13

发表于 2005-7-11 09:57 资料短消息只看该作者

然后讨论能否实现……
N=1003时候，左边1002个来回，右边1002个来回~~来回的数目完全可以对上，也就是说每次都经过第1003根杆子是现实的，但是最后贴一个广告时，不用返回，也就是说只有来没有回，要减掉到最后的杆子第1003根杆子的距离

最后的杆子是1002号或1004号都可以，最后总行程是2010012-1
即2010011

[广告] 《精忠报国岳飞传完整版》火热发布


	英布之勇

组别	士兵
级别	讨逆将军
功绩	6
帖子	630
编号	6578
注册	2004-4-7

#14

发表于 2005-7-11 09:59 资料短消息只看该作者

具体跑法，1003号开始，可以任意地左右来回贴，比如（1，2005，2，2004……）最后以1002号或1004号结束即可。

[广告] 《精忠报国岳飞传完整版》火热发布


	塌鼻子先生

组别	校尉
级别	奋威校尉
功绩	31
帖子	120
编号	41049
注册	2005-6-15

#15

发表于 2005-7-11 10:05 资料文集短消息只看该作者

英布之勇果然英勇了得。可惜功亏一篑，没证明实现的可能性（事实上是不能实现的）。

[广告] 真诚支持说岳，携手共创辉煌


	英布之勇

组别	士兵
级别	讨逆将军
功绩	6
帖子	630
编号	6578
注册	2004-4-7

#16

发表于 2005-7-11 10:09 资料短消息只看该作者

，若以1004为终点，实际上左1002个来回，右1001个来回，差一个来回可以实现的啊……即（左、右、左、右……左、1004）这样每次都经过1003，不犯规吧？

[广告] 《精忠报国岳飞传完整版》火热发布


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

#17

发表于 2005-7-11 11:55 资料文集短消息只看该作者

QUOTE:

原帖由英布之勇于2005-07-11, 10:09:47发表
，若以1004为终点，实际上左1002个来回，右1001个来回，差一个来回可以实现的啊……即（左、右、左、右……左、1004）这样每次都经过1003，不犯规吧？

这就是我的方法，不是最优的。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

#18

发表于 2005-7-11 11:58 资料文集短消息只看该作者

QUOTE:

原帖由英布之勇于2005-07-11, 9:59:49发表
具体跑法，1003号开始，可以任意地左右来回贴，比如（1，2005，2，2004……）最后以1002号或1004号结束即可。

错了，其实要少掉一个第一个的|2005-N|，因为一开始就到了1003，然后从1003开始到1也不经过，

实际上就是你的2010012-1002=2009010，那也就是我的解了。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	英布之勇

组别	士兵
级别	讨逆将军
功绩	6
帖子	630
编号	6578
注册	2004-4-7

#19

发表于 2005-7-11 13:18 资料短消息只看该作者

QUOTE:

原帖由金圭子于2005-07-11, 11:58:53发表
错了，其实要少掉一个第一个的|2005-N|，因为一开始就到了1003，然后从1003开始到1也不经过，

实际上就是你的2010012-1002=2009010，那也就是我的解了。

还是，经过与否只能决定我的路线能否实现，而是否往返才决定路线的长短……1003--1--1003这个往返形成，为什么要减掉1002？

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	loranrowe

组别	士兵
级别	奋威校尉
好贴	1
功绩	6
帖子	143
编号	17767
注册	2004-9-16

#20

发表于 2005-7-11 13:20 资料短消息只看该作者

我错了
简单查了一下，这个问题的一般问题，即间隔距离无特点的该问题
等价于无向图的最长路问题
是一个NP问题
基本上不可能找到通解
看来还是要找特点了，大家继续努力

[广告] 真诚支持说岳，携手共创辉煌


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

#21

发表于 2005-7-11 13:28 资料文集短消息只看该作者

你的意思是：
1003->1->2005->2->2004->3->2003->...->1001->1005->1002->1004

这样么？好像是我误解了，这样的确多一点，多处1002，就是2009010+1002=2010012

其实这个关键是第一个点和最后一个点之间的距离要尽可能小，不然就把把最后一个点放到第一个走（或者反一下），知道两个之间相隔为1，
而如果走完一个循环（就从最后一点再走一次到第一点，完成一个循环）的路程应该是一样的。

[广告] 《精忠报国岳飞传完整版》火热发布


	英布之勇

组别	士兵
级别	讨逆将军
功绩	6
帖子	630
编号	6578
注册	2004-4-7

#22

发表于 2005-7-11 13:58 资料短消息只看该作者

QUOTE:

原帖由金圭子于2005-07-11, 13:28:53发表
你的意思是：
1003->1->2005->2->2004->3->2003->...->1001->1005->1002->1004

这样么？好像是我误解了，这样的确多一点，多处1002，就是2009010+1002=2010012

其实这个关键是第一个点和最后一个点之间的距离要尽可能小，不然就把把最后一个点放到第一个走（或者反一下），知道两个之间相隔为1，
而如果走完一个循环（就从最后一点再走一次到第一点，完成一个循环）的路程应该是一样的。

我的路线长度也只有2010011……

关于走成循环，路线应该是不一样的：（从A1开始）
循环路程S=|A1-A2|+|A2-A3|+|A3-A4|+……+|A2004-A2005|+|A2005-A1|

由于路线肯定要折返走才比较长，所以肯定上式|...|内的值必定正负交替……
S=A1-A2-A2+A3+A3-A4+...-A2004+A2005+A2005-A1
=(A3+A5+A7+...A2005)·2-(A2+A4+A6+...A2004)·2

就是说第一根杆子被牺牲掉了，然后前半部分求最大值，后半部分求最小值

得到S=(1004+1005+...2005)·2-(1+2+3...1002)·2=2010012

若上面1004和1002调换，S值只能是2010008，可见即使是循环线路，也不是一样长的

[广告] 真诚支持说岳，携手共创辉煌


	英布之勇

组别	士兵
级别	讨逆将军
功绩	6
帖子	630
编号	6578
注册	2004-4-7

#23

发表于 2005-7-11 14:16 资料短消息只看该作者

不过根据循环也能推算出路线长度，由于循环最长到2010012（A1=1003时），然后最后去掉循环线路中的一条最短的：1（1003到1002或者是1004）

最后总路线长度的最大值是2010011

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

#24

发表于 2005-7-11 16:43 资料文集短消息只看该作者

喔，我忘了减一了，我最后的1004->1003没减掉。
啊啊啊啊啊啊啊啊啊，看来我是翘鼻子，和塌鼻子无缘，老是做错 T_T

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！