首页 > 代码库 > 欧几里德(辗转相除发)算法

欧几里德(辗转相除发)算法

辗转相除,又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公约数的算法。

此处用函数的递归调用编写了一个小程序:

int gcd(int a,int b)
{
  if(a%b==0)
    return b;
  else
    return gcd(b,a%b);
}

非递归调用则:

int gcd(int a,int b)
{
  int temp;
  while(a%b!=0)
  {
    temp=b;
    b=a%b;
    a=temp;
  }
  return b;
}

通常情况下在gcd(a,b)=1的情况下,通常会要求求出一个数的逆,

int Euclidean(int a,int b,int &c,int &d)
{
  int temp1,temp2;
  if(b%(a%b)==0)//在整除的前一步结束
  {
    c=1;
    d=-a/b;
    return a%b;
   }
  else
  {
    temp2=Euclidean(b,a%b,c,d);//存下前一层返回值
    temp1=d;//对前一层的c,d更新
    d=c-d*(a/b);
    c=temp1;
    return temp2;
  }
}//这里采用的递归调用,

欢迎各位大神指导,小弟感激不尽。。。