C++求最大公约数 |21xrx.com

2023-06-26 18:14:31 深夜i -- --

C++ 最大公约数求解

最大公约数（Greatest Common Divisor，缩写为GCD），这个数学概念在实际的编程中也是有用的。C++是一种强大的编程语言，它提供了很多计算最大公约数的方法。在本文中，我们将介绍一些用C++编程计算最大公约数的方法。

1. 辗转相减法

辗转相减法是一种简单但不太高效的方法，可以计算两个正整数的最大公约数。在每次迭代中，我们都减去另一个数，直到两个数相等。这个相等的数字就是两个数的最大公约数。

下面是一个使用辗转相减法计算两个数的最大公约数的示例：


int gcd(int a, int b)
{
  while(a != b)
  {
    if(a > b)
      a -= b;
    else
      b -= a;
  }
  return a;
}

2. 辗转相除法

辗转相除法，也称为欧几里得算法，是计算两个数的最大公约数的更高效方法。该算法的关键在于用除法而不是减法。

在每个迭代中，我们计算两个数的余数，然后将较小的数作为下一个迭代的除数，将余数作为下一个迭代的被除数。当余数为0时，最后的除数就是两个数的最大公约数。

以下是使用辗转相除法计算两个数的最大公约数的示例：


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

3. STL算法

在C++的标准模板库中，有一个名为__gcd()的函数可以计算两个数的最大公约数。该函数在头文件中定义，在使用前需要包含该头文件。

以下是使用__gcd()函数计算两个数的最大公约数的示例：


#include <numeric>
int gcd(int a, int b)
{
  return __gcd(a, b);
}

以上是计算最大公约数的一些C++编程方法。在实际应用中，根据情况选择不同的方法来计算最大公约数，以便获得更高效的运行时。

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

下一篇: C++中如何将浮点数转化为整型？

()

相似文章