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

2023-07-05 00:23:32 深夜i -- --

C++ 算法最大公约数除法递归

最大公约数是指两个或多个数的公有因数中最大的一个数。在数学和计算机领域中，求最大公约数是一项必须的任务。C++语言提供了多个算法来求最大公约数，下面将介绍其中两种常用的算法。

第一种算法是欧几里得算法，它也被称为辗转相除法。这个算法基于以下定理：如果两个数a和b(a> b)，那么a和b的最大公约数等于b和a%b的最大公约数。换言之，如果r是a除以b的余数，那么a和b的最大公约数等于b和r的最大公约数。这个算法可以用以下C++函数来实现：


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

第二种算法是更相减损法，它基于以下定理：如果两个数a和b(a> b)，那么a和b的最大公约数等于a-b和b的最大公约数。这个算法的性能比欧几里得算法稍差，但在某些情况下会更快。以下是用C++实现它的函数：


int gcd(int a, int b) {
  if (a == b)
    return a;
  
  if (a < b) {
    return gcd(b, a);
  }
  return gcd(a - b, b);
}

以上两个函数都可以通过递归实现，但对于更大的数，可能会导致堆栈溢出，因此使用非递归算法更好。这些算法对于求解最大公约数问题非常有效，可以在较短的时间内求解出最大公约数。如果您需要求最大公约数，那么可以考虑使用其中一个C ++算法。

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

下一篇: C++中关系表达式和逻辑表达式的区别是什么？

()

相似文章