查看完整版本: 分解质因数(5.17重写)

分解质因数(5.17重写)

重写分解质因数这个case,因为原来的代码太难看,还有一点错误

[color=Blue][size=4]一、编写最基本的代码[/size][/color]
最开始我是这么想的，从2开始循环，一直到待分解的那个数为止。用待分解的数去除这个循环变量，如果余数是0，那么这就是待分解的数的一个因数了。
得益于ruby的快捷，我们想到了就可以马上开始做。[code]def dpf(x)
  result = []
  2.upto(x) do |i|
    loop do
      if x % i ==0
        result << i
        x /= i
      else
        break
      end
    end
  end
  result << x unless x == 1
  return result
end[/code]这样分解出来的质因数都存放在result数组里了。

现在我们就可以运行这一小段程序试试。看起来没问题,不过这也太慢了!

[color=Blue][size=4]二、优化程序[/size][/color]

我们不难发现，大于待分解的数的平方根的数不可能是这个数的质因数的，于是我们可以让他只循环到这个数的平方根。[code]def dpf(x)
  #......
  2.upto(x**0.5) do |i|
    #......
  end
end[/code]这样程序就快了不少。来试试他的效率吧！
先算10，他马上就给出了"10 = 2*5"
算100，他也马上给出了"100 = 2*2*5*5"
算1000，算10000
...

等等！
我们好像发现了一个规律。1*10**n = n个2乘n个5。如果我们把这个规律也交给我们的程序的话，那么它看起来就聪明多了。[code]def dpf(x)
  result, xs = [], x.to_s
  if start = (xs =~ /0+$/)
    zeroc = xs.length - start
    result = [2,5] * zeroc
    x = xs[0,start].to_i
  end
  #.......
end[/code]这下对于10的倍数快了些，但对于其他的数还是没有改进。
继续想....
分解质因数，分解质因数，所以不是质数的数就不在我们的考虑范围之内了
事实上，除了2以外，其他的偶数都不是质数。
我们只需要考虑2，和其它奇数，跳过其它偶数[code]def dpf(x)
  #......
  loop do
    if x % 2 ==0
      result << 2
      x /= 2
    else
      break
    end
  end
  3.step((x**0.5).to_i,2) do |i|
    loop do
      if x % i ==0
        result << i
        x /= i
      else
        break
      end
    end
  end
  result << x unless x == 1
  return result.sort!
end[/code]最后，我们的分解质因数的小case的完整的代码在这里[code]def dpf(x)
  raise ZeroDivisionError if x == 0
  result, xs = [], x.to_s
  if start = (xs =~ /0+$/)
    zeroc = xs.length - start
    result = [2,5] * zeroc
    x = xs[0,start].to_i
  end
  loop do
    if x % 2 ==0
      result << 2
      x /= 2
    else
      break
    end
  end
  3.step((x**0.5).to_i,2) do |i|
    loop do
      if x % i ==0
        result << i
        x /= i
      else
        break
      end
    end
  end
  result << x unless x == 1
  return result.sort!
end[/code]

[[i] 本帖最后由 xavier 于 2008-5-17 11:29 编辑 [/i]]

最小的Ruby迷...

xavier，谢谢你，可能你是最小的Ruby迷了吧。
你的小CASE和讲解方式，让我吃了一惊，你才16岁呢。
但你给我们所有学习Ruby的成人很大的信心，你同时告诉我们，学习Ruby不难，只要学和练习就是了！

你做的很好，小Ruby专家。

呵呵，谢谢drive2me
循序渐进的方式是受AWDWR的启发想起来的~

[code]
#filename:
#zhishu.rb
def zhishu(x)
  if x<2
    puts "Error:less then 2"
  else
  result=[]
  y=x
2.upto(y) {|i|
  while y % i == 0
      if y /= i
        result<<i
      end   
  end
}
puts "#{x} = #{result.join("*")}"
end
end
#test
zhishu(123456)
[/code]

[[i] 本帖最后由 aios 于 2007-12-9 01:39 编辑 [/i]]

回复 #4 aios 的帖子

小于2的就只剩0和1了
我觉得为这两个数加个if是不值得的。

就算去掉if，ruby在算法实现的效率上还是最慢的语言
ruby天生就是为了易用，最不考虑的反而是效率

确实，不过可能与算法有关系。再者解释和编译的区别亦明显。

我倒是觉得像ruby这种跑的慢的语言,表面上一眼就能看出能提高效率的地方是一个也不能放过的

[quote]原帖由 [i]xavier[/i] 于 2007-12-9 13:16 发表 [url=http://ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=9090&ptid=704][img]http://ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
我倒是觉得像ruby这种跑的慢的语言,表面上一眼就能看出能提高效率的地方是一个也不能放过的 [/quote]

说的对，赞同。

不得不说，楼主的正则用错了，应该是 /^\d+0+0$/
/^\d+0?0$/ 会匹配所有末尾带0的多位数，比如1010

顺便放上我的答案

[code]
  def g(x)
    2.upto((x ** 0.5).ceil){|i| return i if x%i == 0}
    return x
  end
  
  def f(x)
    v = x
    z = []
    until g(v) == v
      z.push(g(v))
      v /= g(v)
    end
    if z.size == 0
      return [1,x]
    else
      z.push(v)
      return z
    end
  end
[/code]

测试代码
[code]
  for i in 1..50
    p i.to_s + ":" + f(i).join("*")
  end
[/code]

搅和一下，似乎/^\d+0+0$/也不全对，至少没法匹配“10”，是不是用/^\d0+$/就行了？

ps：很喜欢楼主循序渐进的文章，要多努力啊

[quote]原帖由 [i]bbschat[/i] 于 2008-1-16 00:51 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=10502&ptid=704][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
不得不说，楼主的正则用错了，应该是 /^\d+0+0$/
/^\d+0?0$/ 会匹配所有末尾带0的多位数，比如1010...
[/quote]

果真是这样的...

你的实现里头同一个v, g(v)调用了三次，恐怕有效率问题吧
虽说ruby不强调效率，但如此浪费CPU有欠不妥

[quote]原帖由 [i]bbschat[/i] 于 2008-1-16 00:51 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=10502&ptid=704][img=13,13]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
不得不说，楼主的正则用错了，应该是 /^\d+0+0$/
/^\d+0?0$/ 会匹配所有末尾带0的多位数，比如1010

顺便放上我的答案


  def g(x)
    2.upto((x ** 0.5).ceil){|i| return i if x%i == 0}
    return x
... [/quote]