jtahstu的博客

root@jtahstu.com   Github   英文博客  

最新碎语:以后没事写写小的知识点吧

您的位置:jtahstu的博客 >算法> 欧几里德算法求最大公约数 - Ruby

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

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: http://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中国大陆许可协议 进行许可,欢迎转载,演绎或用于商业目的。

---

二维码加载中...

扫一扫移动端访问O(∩_∩)O

发表评论

96 + 29 =
路人甲 表情
看不清楚?点图切换 Ctrl+Enter快速提交
正在加载中……