软件编程
位置：首页>> 软件编程>> C语言>> 详解C语言求两个数的最大公约数及最小公倍数的方法

详解C语言求两个数的最大公约数及最小公倍数的方法

作者：wuzhekai1985　　发布时间：2022-02-28 01:17:25　

标签：公约数,公倍数

求两个正整数的最大公约数 

     思路：这是一个很基本的问题，最常见的就是两种方法，辗转相除法和辗转相减法。通式分别为 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;
}
0
投稿

猜你喜欢

手机版 软件编程 asp之家 www.aspxhome.com