首页 >后端开发 >C++ >计算最大公因数的C++程序

计算最大公因数的C++程序

王林
王林转载
2023-09-18 13:09:111609浏览

计算最大公因数的C++程序

最高公因数或最大公约数是能够在不产生任何余数的情况下,能够同时整除两个或多个值的因数。在本文中,我们将讨论在C++中执行两个数字的HCF / GCD的几种方法。

这只是一个数学解决方案,有几种算法可以找到最大公约数。欧几里得方法是常见的找到最大公约数的方法。我们将在迭代模式和递归模式下使用相同的算法。

使用迭代方法

欧几里德求最大公约数的迭代解法在算法部分中展示。

算法

  • 将两个数a和b作为输入。
  • 如果a等于0,则返回b。
  • 如果 b 为 0,则返回 a。
  • 当a和b不相同时,执行操作。
    • 如果 a > b,则 a := a – b。
    • 否则 b := b - a。
  • 结束循环。
  • 将最大公因数作为变量 a 返回。

示例

#include <iostream>
using namespace std;

int solve( int x, int y) {
   if (x == 0)
      return y;
   else if (y == 0)
      return x;
   while (x != y) {
      if (x > y)
         x = x - y;
      else
         y = y - x;
   }
   return x;
}

int main( int argc, char* argv[] ) {
   cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl;
   cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) <<   endl;
   cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl;
   cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl;
}

输出

HCF of two numbers 12 and 72 is: 12
HCF of two numbers 18 and 13 is: 1
HCF of two numbers 117 and 96 is: 3
HCF of two numbers 85 and 15 is: 5

使用迭代方法

可以使用递归方法来实现相同的欧几里得方法。下面我们将描述递归方法的定义,如下所示的算法。

算法

  • 定义一个名为HCF的函数,该函数接受两个数字a和b。
  • 如果a为0,则返回b
  • 否则返回 HCF( b mod a, a)

示例

#include <iostream>
using namespace std;

int solve( int x, int y) {
   if (x == 0)
      return y;
   return solve( y % x, x );
}

int main( int argc, char* argv[] ) {
   cout << "HCF of two numbers 12 and 72 is: " << solve(12, 72) << endl;
   cout << "HCF of two numbers 18 and 13 is: " << solve(18, 13) << endl;
   cout << "HCF of two numbers 117 and 96 is: " << solve(117, 96) << endl;
   cout << "HCF of two numbers 85 and 15 is: " << solve(85, 15) << endl;
}

输出

HCF of two numbers 12 and 72 is: 12
HCF of two numbers 18 and 13 is: 1
HCF of two numbers 117 and 96 is: 3
HCF of two numbers 85 and 15 is: 5

结论

在解决不同数学问题时,求最大公因数或最大公约数是非常有用的。可以使用欧几里得方法来计算。这个方法可以迭代地应用,也可以递归地应用。这里我们展示了两种方法。另一方面,我们可以通过最小公倍数(LCM)来计算GCD/HCF。两个数的GCD和LCM与这两个数的乘积相同。因此,根据这个原理,如果我们知道这两个数的LCM和乘积,就可以很容易地计算出GCD。

以上是计算最大公因数的C++程序的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除