查看完整版本: 2008-05-26 Ruby 测试题(00017)

2008-05-26 Ruby 测试题(00017)

F(n) = 1 + 2 + ,..., + n = (1+n)*n/2
求最小的n，使F(n)拥有超过500个的约数。

本题取自Euler-12，不难，但求一个效率解。

Euler12我做的是6s, 源码在11页上面.

比我快许多啊，受制约与求约数的方法，后面好几道题目都失控与效率。

这一题做了好长时间, 是由于实现下面的想法的时候引入了一个小BUG.
**** Hidden Message *****

[[i] 本帖最后由 5swords 于 2008-5-26 21:11 编辑 [/i]]

啊，prime_division，我嫌判断素数麻烦，所以没用这个。

回复 5# 的帖子

所有的约数都是素数的积, 拿到所有的素数就是所有的约数了啊.
24 = [[2,3],[3,1]]
2**0 * 3**0 , 2**3 * 3**1=> 1 * 24
2**1 * 3**0 , 2**2 * 3**1=> 2 * 12
2**2 * 3**0 , 2**1 * 3**1=> 4 * 6
2**3 * 3**0 , 2**0 * 3**1=> 8 * 3

所有约数的个数: 8  = (3+1) * (1+1)

这个我知道，我也是这么算的，只是在分解的时候没有用prime_division而是自己笨来的。[code]def Euler12(x)
factor = 0
num = 1
while factor <= x
  num += 1
  tr = (1+num)*num/2
  arr=[]
  n = 2
  tt = tr
  kk = 1
  while tt != 1
    if tt % n == 0 then
      kk += 1
      tt = tt / n      
    else
      arr<<kk
      kk = 1
      n += 1
    end
  end
  arr<<kk
  factor = 1
  arr.each {|h|
    factor *= h
  }  
end
puts tr, "\n"
end
#test
Euler12(500)[/code]慢很多

看来我们做过EULER这题的, 在这儿太早讨论有点不好的说...:L

看看6秒怎么算的，为什么我算要半分钟，差距太大了

重构了一下我的程序, 可能做one liner有点过了:
**** Hidden Message *****--------------------------
exp1 until exp2
等价于
until exp2
  exp1
end
exp2至少运行一次, exp1 while exp2也一样.

如果要做C一样的do ... while的话
应该是 (until一样)
begin
...
end while exp[code]#test
def geti(i)
  p i
  i
end
i = 1
begin
i += 1
end while geti(i) < 3
#=>2
#=>3
i = 1
i += 1 while geti(i) < 3
#=>1
#=>2
#=>3[/code]

[[i] 本帖最后由 5swords 于 2008-5-29 19:00 编辑 [/i]]