21xrx.com
2025-07-08 22:00:31 Tuesday
文章检索 我的文章 写文章
C++如何求最小公倍数
2023-06-30 11:54:46 深夜i     14     0
C++ 最小公倍数 求解

最小公倍数(LCM)指的是两个或多个数的公共倍数中最小的那个。在C++里使用递归和辗转相除法来求解最小公倍数。

首先,我们需要定义一个函数来求最大公约数(GCD):

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

接着,我们可以使用最大公约数来求得最小公倍数:

int LCM(int a, int b) {
 return (a * b) / GCD(a, b);
}

这个函数使用了公式:两个数的积等于它们的最大公约数和最小公倍数的积。因此,只需要调用GCD函数来求得最大公约数,然后乘以两个数的积再除以最大公约数,就可以得到它们的最小公倍数了。

但这种方法只适用于两个数的情况。对于多个数的情况,我们可以使用递归来处理。具体的,我们可以把前两个数求得的最小公倍数再和下一个数求最小公倍数,以此类推,一直到处理完所有的数。下面是代码实现:

int LCM(int arr[], int n) {
 if (n == 1) {
  return arr[0];
 } else {
  return LCM(arr[0], LCM(&arr[1], n - 1));
 }
}

这个函数将数组的第一个元素和剩余的元素一起递归调用自己,直到数组中只剩下一个元素。如果数组中只有一个元素,则返回该元素作为最小公倍数。

总之,C++里可以使用递归和辗转相除法来求得最小公倍数。对于两个数的情况,我们可以直接套用公式;对于多个数的情况,我们可以使用递归来处理。

  
  

评论区