求最大公约数的两种算法 ________________________________________ 辗转相除法和移位相减法（Euclid & stein 算法） 给出Stein算法如下： 1.    如果A=0，B是最大公约数，算法结束 2.    如果B=0，A是最大公约数，算法结束 3.    设置A1 = A、B1=B和C1 = 1 4.    如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可) 5.    如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 6.    如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 7.    如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn 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; }  

评论