作者：未知 来源：月光软件站 加入时间：2005-5-13　月光软件站

辗转相除法和移位相减法（Euclid & stein 算法）

给出Stein算法如下：

1. 如果A=0，B是最大公约数，算法结束
2. 如果B=0，A是最大公约数，算法结束
3. 设置A₁ = A、B₁=B和C₁ = 1
4. 如果A_n和B_n都是偶数，则A_n+1 =A_n /2，B_n+1 =B_n /2，C_n+1 =C_n *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可)
5. 如果A_n是偶数，B_n不是偶数，则A_n+1 =A_n /2，B_n+1 =B_n ，C_n+1 =C_n (很显然啦，2不是奇数的约数)
6. 如果B_n是偶数，A_n不是偶数，则B_n+1 =B_n /2，A_n+1 =A_n ，C_n+1 =C_n (很显然啦，2不是奇数的约数)
7. 如果A_n和B_n都不是偶数，则A_n+1 =|A_n -B_n|，B_n+1 =min(A_n,B_n)，C_n+1 =C_n
8. n++，转4

//greatest common divisor
//by heaton
//2005/03/11

#include <iostream>

using namespace std;

//交换a ，b的值
void swap(int& a1,int &b1)
{
    int temp;
    temp=a1;
    a1=b1;
    b1=temp;
} 
  
//辗转相除法
int gcd(int a,int b)
{
    if(a < b)swap(a,b);
    int c=a%b;
    //cout<<"辗转相除法\n"<<"a   b\n"<<a<<" "<<b<<"\n";
    while(c!=0)
    {
        a=b;
        b=c;
        cout<<a<<" "<<b<<"\n";
        c=a%b;
    }
    return b;    
}

//移位相减法
int gcd2(int a,int b)
{
    if(a < b)swap(a,b);
 //cout<<a<<" "<<b<<endl;//跟踪a，b的值
    if(a==0)return b;
    if(b==0)return a;
    while(a != b)
    {
       
        if(( (a&1) == 0 ) && ( (b&1) == 0 )){
            return 2*gcd2(a/2,b/2); //a,b are even numbers
        }else if(( (a&1) == 1 ) && ( (b&1) == 0)){
            return gcd2(a,b/2); //a is odd number , b is even number
        }else if(((a&1) == 0 ) && ( (b&1) == 1) ){
            return gcd2(a/2,b);//a....even   ;b ...odd ...
        }else if(((a&1) == 1 ) && ((b&1) == 1)){
            return gcd2(b,(a-b)); //a,b are odd numbers
        }   
    } 
    return b; 
}

//通过递归调用求n个数的最大公约数 
int ngcd(int a[],int n)
{ 
 
  if (n==1)
 return a[0];
  else
 return gcd2(a[n-1],ngcd(a,n-1));
}

int main()
{
 int m=gcd(15,25);
 cout<<m<<"\n 移位相减法\na   b\n";
 int n=gcd2(15,20);
 cout<<n<<"\n the common divisor of array {450,90,15,45} \n";
 int a[]={450,90,15,45};//应该先按升序对数组排序
 int x=ngcd(a,4);
 cout<<" value:"<<x<<endl;///??????
 return 0;
} 

相关软件：