当前位置:   article > 正文

简单经典算法——欧几里德算法(求最大公约数)_欧几里得辗转相除法球最大公约数需要要求几次

欧几里得辗转相除法球最大公约数需要要求几次

 k_eckelhttp://www.mscenter.edu.cn/blog/k_eckel & http://k-eckel.cnblogs.com

 

前几天和一位老师聊天,老师是一位很实干的老师,刚从英国回来。说到去给一个公司招聘面试时候,对着10几个计算机专业的研究生让写一个求最大公约数的欧几里德算法,连思想都给出了,竟然…..。我无语,想想自己在很多时候也对基础的简单的经典的算法有些忽略了,心有余悸。

欧几里德算法也就是辗转相除法,有着2000年的历史了。欧几里德算法依据的算法理论是一个定理:gcd(a,b) = gcd(b,a mod b)

实现源码为:

//递归实现

int gcd(int m,int n)

{

       if (m < n)

       {

              int tmp = m;

              m = n;

              n = tmp;

       }

 

       if (n == 0)

              return m;

       else

              return gcd(n,m % n);

}

//非递归实现

int gcd2(int m,int n)

{

       if (m < n)

       {

              int tmp = m;

              m = n;

              n = tmp;

       }

 

       if (n == 0)

              return m;

      

       while (n > 0)

       {

              int tmp = m % n;

              m = n;

              n = tmp;

       }

 

       return m;

}

       这里给出了最大公约数的算法,那怎么求最大公倍数呢?其实知道了最大公约数,最小公倍数的求法就简单了:

int gbs(int m,int n)

{

       return m*n/gcd(m,n);

}

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号