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

本帖隐藏的内容需要回复才可以浏览

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

本帖隐藏的内容需要回复才可以浏览

本帖隐藏的内容需要回复才可以浏览

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

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

本帖隐藏的内容需要回复才可以浏览

我的好长啊。。

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

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

[Copy to clipboard] [ - ]

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)

引用:

原帖由 liumuqing 于 2008-3-24 18:56 发表
呜呜 。。没脸活了。。。楼上的都好短。。。。。

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

本帖隐藏的内容需要回复才可以浏览

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

本帖隐藏的内容需要回复才可以浏览

我还得努力

试一下下

本帖隐藏的内容需要回复才可以浏览

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

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

试试看

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)

本帖隐藏的内容需要回复才可以浏览

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

这题比较简单，呵呵！

本帖隐藏的内容需要回复才可以浏览