最贵族约数最小公倍数

最大公约数最小公倍数
好吧，说实话是实在不喜欢算法，因为我数学一直很垃圾，150分的题，高中三年，150分的题，很少有上90的情况，99%是在70分上下晃悠，唉，很惭愧。这直接导致了我对数学的恐惧，毕业后走上了编程的道，发现还是有很多的算法，每次遇到算法我就傻，这里只是我的一些小记录，算是给自己的脑袋开开窍吧。
1、求最大公约数：
   假设有整数x，y，要求这两个数的最大公约数，怎么做？首先思路分析：先求出x和y中较小的数i，然后至i到0循环所有整数，第一个能被x和y整除的数即为最大公约数。

def gcd(x,y)   i = x#假设x是两个数中最小的那个数，并赋值给i   if x > y      i = y#如果y比x小，那么将y赋值给i   end   while i > 0 #从i开始循环，每循环一次，i减小一个数，如果i大于0，那么一直循环里面的内容      if x % i == 0 and y % i == 0         return i #如果第一个数能够同时被x和y整除，那么这个数就是最大公约数      else         i -= 1#如果前一个数不能整除x和y，那么就减小一个数再整除x和y，以此循环      end   endend

以上的思路已经整理清楚了，但是太复杂了，能不能短一点：

def gcd2(x, y)   i = x   i = y if x > y   #i.downto(1)表示从i(两个数中最小的那个数)累减到0，每累减一次，拿到当前的数值，并传给后边的block，如果block中的条件满足，就返回当前的数值   i.downto(1) {|j| return j if x%j==0 and y%j==0}end

能不能再短一点:

def gcd3(x,y)   #与上边的方法相比，downto函数是从两个数的和开始的，这是因为省略了判断两个数大小的判断   (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#循环条件，如果y!=0就进入循环操作      r = x % y#r作为x除以y的余数      x = y #将y赋值给x      y = r #将余数赋值给y，如果y，即上一次运算的余数不为0，则继续循环   end   return xend

能不能即快又短
如果改成递归，可以简写成这样：

def gcd5(x,y)   x,y = y,x if x<y#将大数赋值给x，小数赋值给y   y==0 ? x : gcd5(x%y, y)#如果小数为0，则两个数的最大公约数为最大的数，否则，就用辗转相除法计算end

上面的写法虽然只有两行但还是感觉有点多，能不能把x与y比较大小的也省去：

def gcd6(x, y)   y == 0 ? x : gcd6(y, x%y) #若 r 是 a ÷ b 的余数, 则gcd(a,b) = gcd(b,r)end

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

GCD * LCM = x * y

所以可以通过gcd来算lcm:

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

好吧，如果我要求用一行代码写出来，求两个数的最小公倍数怎么写：
比如说我要求6和9的最小公倍数：

#因为任意两个数x和y，他们的最小公倍数的取值区间在1和x*y之间，那么我就从最小的一开始循环去试，如果这其中的第一个值满足了除以x 余数为0 并且 满足了除以y余数也为0，那么这个数就是最小的公倍数1.upto(6*9){|j| return j if j%6 == 0 && j%9 == 0 }

查看更多 下一篇