[关闭]
@jtahstu 2017-06-07T10:00:21.000000Z 字数 391 阅读 2202

欧几里德算法求最大公约数

算法


欧几里德算法又称辗转相除法,用于计算两个整数m, n的最大公约数。

其计算原理依赖于下面的定理:

gcd(m, n) = gcd(n, m mod n)

这个定理的意思是:整数m、n的最大公约数等于n和m除以n的余数的最大公约数。

  1. # author: jtusta
  2. # contact: root@jtahstu.com
  3. # site: http://www.jtahstu.com
  4. # software: RubyMine
  5. # time: 2017/6/7 14:44
  6. class Gcd
  7. # 循环写法,即非递归写法
  8. def gcd(m, n)
  9. while n>0
  10. m, n = n, m % n
  11. end
  12. return m
  13. end
  14. # 递归写法
  15. def gcd_2(m,n)
  16. return n==0?m:self.gcd_2(n,m%n)
  17. end
  18. end
  19. c = Gcd.new
  20. res = c.gcd(8,12)
  21. puts res
  22. rec = c.gcd_2(32,24)
  23. p rec
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注