查看完整版本: 2008-03-24 Ruby 测试题(00005)

2008-03-24 Ruby 测试题(00005)

今天还是来做点基础的。
输出2个整数（a,b）的最大公约数和最小公倍数。
暂时不考虑溢出以及负数，0的问题。
不知道Math库里是不是已经有轮子在，就算在，也先别用吧。
**** Hidden Message *****

貌似前两天刚优化过~直接贴答案

**** Hidden Message *****

**** Hidden Message *****

[[i] 本帖最后由 xavier 于 2008-3-25 13:29 编辑 [/i]]

楼上的试一下puts gcd(24,15)

**** Hidden Message *****

我的好长啊。。

呜呜 。。没脸活了。。。楼上的都好短。。。。。

首先，从算法上来讲，求最大公约数没必要把所有质因数都找出来，虽然这是一种方法。但是大数组操作的效率是有问题的。
其次，最大公约数×最小公倍数=两数乘积。
代码上来讲，求质因数的时候没必要把2独立出来。如果确实把2单独写了，那后面那个循环步长就应该是2而不是一。
然后，利用下Ruby的特性，可以把代码也搞得短一点的。
[code]
def get_all_prime_factor(n)
  answer = []
  x = 2
  while n != 1
    if n % x == 0
      n /= x
      answer.push(x)
    else
      x += 1
    end
  end
  return answer
end

def greatest_common_divisor(a, b)
    a_factor = get_all_prime_factor(a)
    b_factor = get_all_prime_factor(b)
    answer = 1
    a_factor.each {|i| answer *= b_factor.delete(i) if b_factor.include?i}
    return answer
end

def lease_common_multiple(a, b)
    a_factor = get_all_prime_factor(a)
    b_factor = get_all_prime_factor(b)
    answer = a * b
    a_factor.each {|i| answer /= b_factor.delete(i) if b_factor.include?i}
    return answer
end

#test
puts greatest_common_divisor(15, 12)
puts lease_common_multiple(12, 15)
[/code]

[quote]原帖由 [i]liumuqing[/i] 于 2008-3-24 18:56 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=12996&ptid=3898][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
呜呜 。。没脸活了。。。楼上的都好短。。。。。 [/quote]

正确，然后优化。不怕，熟能生巧！继续！

**** Hidden Message *****

稍微拓展了一下，求n个数的最大公约数和最小公倍数

我还得努力

试一下下
**** Hidden Message *****
记得小时候我爷爷教过我，“辗转相除法”
我确定名字没记错，虽然没用到除法但真的叫这个名字……

[[i] 本帖最后由 hexawing 于 2008-6-15 09:08 编辑 [/i]]

试试看

def gcd(a,b)
  a,b = b,a if a<b
  if a%b != 0
    return gcd(b,a%b)
  else
    return b
  end
end

def lcm(a,b)
  return a*b/gcd(a,b)
end

puts gcd(13,48)
puts lcm(13,48)

**** Hidden Message *****

[[i] 本帖最后由 neohsiao 于 2008-7-13 17:42 编辑 [/i]]

这题比较简单，呵呵！
**** Hidden Message *****

直接来看看答案

[code]**** Hidden Message *****[/code][code]>ruby bbs324.rb
4560
6540
60
497040
>Exit code: 0[/code]

比较下算法！呵呵

看看答案

看看答案