C++求最小公约数的方法 |21xrx.com

C++求最小公约数的方法

2023-07-05 00:56:52 深夜i 11 0

C++ 求最小公约数方法

C++作为一种高级编程语言，在数学计算方面有着强大的功能，其中求最小公约数也不例外。以下是C++求最小公约数的方法。

首先，我们需要明确什么是最小公约数。最小公约数是指两个或多个整数的公共约数中最小的一个数。例如，12和18的公共约数有1、2、3、6，其中最小的是2，因此，它们的最小公约数为2。

C++中求最小公约数的方法有多种，例如：

1. 枚举法

枚举法是最直观的一种求最小公约数的方法，其代码如下：

int gcd(int a, int b) {
  int min_num = a < b ? a : b;
  for (int i = min_num; i >= 1; i--) {
    if (a % i == 0 && b % i == 0)
      return i;
    
  }
  return 1;
}

2. 辗转相除法

辗转相除法是一种更加高效的求最小公约数的方法，其代码如下：

int gcd(int a, int b) {
  int r;
  while (b != 0)
    r = a % b;
    a = b;
    b = r;
  
  return a;
}

以上两种方法可以求出两个数的最小公约数，如果要求多个数的最小公约数，可以使用递归来实现。递归方法的代码如下：

int gcd(int a, int b) {
  if (b == 0)
    return a;
  
  return gcd(b, a % b);
}
int multi_gcd(const vector<int>& arr) {
  if (arr.size() == 1) {
    return arr[0];
  }
  int a = arr[0];
  for (int i = 1; i < arr.size(); i++) {
    int b = arr[i];
    a = gcd(a, b);
  }
  return a;
}

以上就是C++求最小公约数的方法。不同的方法有不同的适用场景，可以根据实际情况选择合适的方法。

上一篇: idea打包java可执行jar包

下一篇: C++错误查看方法

评论区

相似文章