@jtahstu 2017-06-07 14:58 字数 406 阅读 0
欧几里德算法求最大公约数
算法
欧几里德算法又称辗转相除法，用于计算两个整数m, n的最大公约数。
其计算原理依赖于下面的定理：
gcd(m, n) = gcd(n, m mod n) 这个定理的意思是：整数m、n的最大公约数等于n和m除以n的余数的最大公约数。
# author: jtusta
# contact: root@jtahstu.com
# site: https://www.jtahstu.com
# software: RubyMine
# time: 2017/6/7 14:44
class Gcd
# 循环写法，即非递归写法
def gcd(m, n)
while n>0
m, n = n, m % n
end
return m
end
# 递归写法
def gcd_2(m,n)
return n==0?m:self.gcd_2(n,m%n)
end
end
c = Gcd.new
res = c.gcd(8,12)
puts res
rec = c.gcd_2(32,24)
p rec
Markdown版 https://zybuluo.com/jtahstu/note/777987
---
本文章采用 知识共享署名2.5中国大陆许可协议 进行许可，转载必须注明作者和本文链接。
---
发表评论