[第29期]捡金币(已结)

agstick

[此贴子已经被作者于2007-12-2 15:26:09编辑过]

songhuaegg

答案已发送,邮箱地址songhuaegg@163.com

速度比较慢,要65秒

我再想想更快的办法

 

递归算法，结果有误，数据多时很慢。

 

[此贴子已经被agstick于2007-11-24 21:13:48编辑过]

False

只做好第一步

还得多多学习啊

Luckyguy2008

已发邮件给版主，请批阅，谢谢！

递归穷举＋动态规划，结果正确，数据多时较慢。

 

[此贴子已经被agstick于2007-11-24 21:47:39编辑过]

fjlhgs

答题已发送至agstick@126.com。

递归穷举法，结果正确，速度太慢，30个以上金币就很难等到结果出来了。

[此贴子已经被agstick于2007-11-25 0:05:33编辑过]

willin2000

答案发送至：agstick@126.com,跟贴占位.

运行速度似乎还可以(不到1秒).

双线程动态规划法，正解。

 

[此贴子已经被agstick于2007-11-25 0:07:57编辑过]

泓()

答案发送至：agstick@126.com,跟贴占位.

常规循环，结果有误，注意是2次，第一次最大的并不一定是最优的路线。

[此贴子已经被agstick于2007-11-25 0:15:16编辑过]

彭希仁

答案发送至：agstick@126.com,

不好意思我总共发送过好多个答案,

第一次发的计算结果错了,有可能找的不是最大值

第二次发的是对的,可惜太慢

.............

最后一次发的答案,速度上经过多次优化(也就是对递归作了剪枝处理),98个金币可在0.4秒左右完成.

不错，递归都赶上动态规划了

 

[此贴子已经被agstick于2007-11-26 21:16:45编辑过]

ldy888

对此题兴趣比较大。重新作了。邮件已发

两个方案

1、速度很快（楼上有速度表），但某些数情况下 来回程所选的最大值是错误的

2、思路与方法1大都相同， 多了循环历遍比较 结果正确，速度比方法1 慢

方法2 速度表 ：

20 个金币  0.1 秒左右

25个       0.3秒 左右

35个       1 秒 左右

40 个      2-3秒

60个       70-150秒

60个以上 没试过

98 个       估计 1-2 天

还好题目没对金币数量要求

 

第一种递归方法正确，速度较慢。

[此贴子已经被agstick于2007-11-26 21:31:39编辑过]

上清宫主

同楼上，第一个很快写出来了，第二个得再想想。还是占个位吧！

谢谢楼主！

当时回复时可只到9楼，故写了“同楼上”，那时就要发我写的，结果回复后没见到自己的回复内容，就主观认为可能是级别不够。所以没有发。

现在来学习各位大师的杰作也好！

再次谢谢楼主！

[此贴子已经被作者于2007-11-28 15:20:58编辑过]