Ruby迷

最近在微博上闲扯出最大公约数（GCD：greatest common divisor）和最小公倍数的算法（LCM：Least Common Multiple）的话题，虽然算法并不难，但整理一下。

有神眼网友马上指出GCD是”gong ch*n da*g“的缩写，不禁麻花一紧，希望此贴不会被qiang。

首先要实现它，Just do it

GCD简单来说就是: 能被x和y整除的最大的数，因些有了这个算法：
先求出x和y中较小的数i，然后至i到0循环所有整数，第一个能被x和y整除的数即为最大公约数。

def gcd(x,y)
   i = x
   if x > y
      i = y
   end
   while i > 0
      if x % i == 0 and y % i == 0
         return i
      else
         i -= 1
      end
   end
end

能不能短一点

上面的代码看起来很累赘，让我们来发挥Ruby的Magic，简写如下：

def gcd2(x, y)
   i = x
   i = y if x > y
   i.downto(1) {|j| return j if x%j==0 and y%j==0}
end

运用到了downto和闭包，5.downto(1)会依次返回5,4,3,2,1

能不能再短一点

def gcd3(x,y)
   (x+y).downto(1) {|j| return j if x%j==0 and y%j==0}
end

只有一行代码，很有喜感吧。

能不能快点

上面算法虽然能求出结果，但效率应该是最低的，其实有个算法被公认为求GCD的最快算法，学名叫叫“辗转相除法”

辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余数, 则gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。

直接来个实现的代码

def gcd4(x,y)
   while y != 0
      r = x % y
      x = y
      y = r
   end
   return x
end

能不能即快又短

如果改成递归，可以简写成这样

def gcd5(x,y)
   x,y = y,x if x<y
   y==0 ? x : gcd5(x%y, y)
end

最快且短？

上面的写法虽然只有两行但还是感觉有点多，能不能把x与y比较大小的也省去，想了好久也没结果。后面多谢网友“Sanatir”给的答案，写法很巧秒，与gcd5区别只是递归时交换了参数的位置，赞！

def gcd6(x, y)
   y == 0 ? x : gcd6(y, x%y)
end

不确定这是否是最快且短的答案，希望还能再优化，哈哈～

最小公倍数

到现在为止，还没谈到最小公倍数LCM。一直不说，是因为有个神奇的公式。

GCD * LCM = x * y

果断写出：

def lcm(x,y)
   x * y / gcd(x,y)
end

一行搞定绰绰有余哈~~~

如果你有更好实现，欢迎回帖，共同分享，谢谢~~~
如果其它语言有更Magic的写法，欢迎贴出来与Ruby PK啊~~~