詳解C說話求兩個數的最年夜條約數及最小公倍數的辦法

詳解C說話求兩個數的最年夜條約數及最小公倍數的辦法。本站提示廣大學習愛好者：（詳解C說話求兩個數的最年夜條約數及最小公倍數的辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是詳解C說話求兩個數的最年夜條約數及最小公倍數的辦法正文

求兩個正整數的最年夜條約數 

     思緒：這是一個很根本的成績，最多見的就是兩種辦法，展轉相除法和展轉相減法。通式分離為 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0)。依據通式寫出算法不難，這裡就不給出了。這裡給出《編程之美》上的算法，重要是為了削減迭代的次數。
     關於x和y，假如y = k * y1, x= k * x1，那末f(x, y) = k * f(x1, y1)。別的，假如x = p * x1，假定p為素數，而且y % p != 0，那末f(x, y) = f(p * x1, y) = f(x1, y)。取p = 2。

參考代碼：

//函數功效: 求最年夜條約數 
//函數參數: x,y為兩個數 
//前往值:  最年夜條約數 
int gcd_solution1(int x, int y) 
{ 
  if(y == 0) 
    return x; 
  else if(x < y) 
    return gcd_solution1(y, x); 
  else 
  { 
    if(x&1) //x是奇數 
    { 
      if(y&1) //y是奇數 
        return gcd_solution1(y, x-y); 
      else  //y是偶數 
        return gcd_solution1(x, y>>1); 
    } 
    else //x是偶數 
    { 
      if(y&1) //y是奇數 
        return gcd_solution1(x>>1, y); 
      else  //y是偶數 
        return gcd_solution1(x>>1, y>>1) << 1; 
    } 
  } 
} 

求最小公倍數：
最經常使用的是展轉相除法，有兩整數a和b：
① a%b得余數c
② 若c=0，則b即為兩數的最年夜條約數
③ 若c≠0，則a=b，b=c，再歸去履行①

上面非遞歸版本：

int gcd_solution2(int x, int y) 
{ 
  int result = 1; 
  while(y) 
  { 
    int t = x; 
    if(x&1) 
    { 
      if(y&1) 
      { 
        x = y; 
        y = t % y; 
      } 
      else 
        y >>= 1; 
    } 
    else 
    { 
      if(y&1) 
        x >>= 1; 
      else 
      { 
        x >>= 1; 
        y >>= 1; 
        result <<= 1; 
      } 
    } 
  } 
  return result * x; 
}