jmouse 2008-5-14 16:37
2008-05-14 Ruby 测试题(00016)
最近局面有点惨淡。不知道是不是题目偏难。
其实，个人认为这些题目都是比较基础的，说实话，并不是Ruby所独有的。
今天延续回溯的例子，也许是最后一个了吧。
给定自然数N，请给出N的加法分解式。
例如：N=5，则输出：
5=4+1
5=3+2
5=3+1+1
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
xavier 2008-5-15 13:20
用纸写然后敲上来的，没仔细测试，不知有没有错
**** Hidden Message *****[code]5.additive_partition
#=>5=4+1
5=3+1+1
5=2+1+1+1
5=1+1+1+1+1
5=2+2+1
5=3+2[/code]
5swords 2008-5-15 16:11
**** Hidden Message *****
--------------------------
"5 = 4 + 1"
"5 = 3 + 2"
"5 = 3 + 1 + 1"
"5 = 2 + 2 + 1"
"5 = 2 + 1 + 1 + 1"
"5 = 1 + 1 + 1 + 1 + 1"
---------------------------
优化版，除打印之外，速度是原来的三倍。
接下来就不知道该怎么优化了，不会用benchmark，请大家指点。
**** Hidden Message *****
--------------------
再快一点点的版本, 但是不好看.
**** Hidden Message *****
[[i] 本帖最后由 5swords 于 2008-5-19 10:13 编辑 [/i]]
jmouse 2008-5-16 09:55
评分系统有问题啊。
Xavier看一下你的6=2+2+2去了哪里？
jmouse 2008-5-19 10:47
呵呵，共同进步。
其实，我出这道题目还有个原因，是因为我对付不了EULEA上的那个100。
5swords 2008-5-19 16:46
看不出和EULER100有什么联系, 好奇ing...
jmouse 2008-5-19 17:01
不是第100题，是76题。
我能出50，80，但是100我没耐心，所以要寻求个好方法。
目前在想，Xavier的思路可以用。
maojiajia228 2008-5-20 19:51
看答案。。
plucury 2008-5-20 23:09
**** Hidden Message *****
如5swords 所言，这样更精简些：）
[[i] 本帖最后由 plucury 于 2008-5-21 15:42 编辑 [/i]]
5swords 2008-5-21 13:28
回复 12# 的帖子
循环可以从n-m开始吗?
可以从[0,n-m].max开始, 循环里的if就可以不要了.
[[i] 本帖最后由 5swords 于 2008-5-21 13:51 编辑 [/i]]
5swords 2008-5-21 14:19
改了下plucury的代码, 把输出去掉再加上hash, euler76可以0.4秒搞定.
意外的收获~ :)
谢谢plucury!
5swords 2008-5-22 08:42
**** Hidden Message *****
[[i] 本帖最后由 5swords 于 2008-5-22 11:00 编辑 [/i]]
jmouse 2008-5-23 09:48
看来5SWORDS的机器也很强大，我笔记本上算100要0.68秒
5swords 2008-5-23 11:14
我只是改了一点代码, 算法照抄plucury. 说实在的, 我现在还不知道plucury为什么这么做.
:)单位的机器还是可以的.
[[i] 本帖最后由 5swords 于 2008-5-23 11:22 编辑 [/i]]
plucury 2008-5-23 17:19
[quote]原帖由 [i]5swords[/i] 于 2008-5-23 11:14 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=15890&ptid=4700][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
我只是改了一点代码, 算法照抄plucury. 说实在的, 我现在还不知道plucury为什么这么做.
:)单位的机器还是可以的. [/quote]
做了hash速度提升很多阿。。**** Hidden Message *****ps.5swords的代码我看了好久,ruby还得好好努力啊.
attraction 2008-5-25 01:44
看看答案
bbschat 2008-5-25 14:49
最近新带一个项目，因为客户安全需求不能上网，只能周末上来看看，大家加油！
diyixinlang 2008-5-25 17:23
看看答案!
看看大家的答案!