21xrx.com
2024-11-05 16:30:29 Tuesday
登录
文章检索 我的文章 写文章
C++求最小公约数的方法
2023-07-05 00:56:52 深夜i     --     --
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++求最小公约数的方法。不同的方法有不同的适用场景,可以根据实际情况选择合适的方法。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复