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

2023-07-06 15:56:32 深夜i -- --

C++ 最大公约数代码

C++代码实现最大公约数，是一种非常基础的算法，也是初学者必须学习的。下面将介绍C++语言是如何求最大公约数的。

在C++中，可以使用两种算法来求最大公约数，分别是辗转相除法和更相减损术。辗转相除法是最常用的算法，其实现思路很简单，就是将两个数中的大数除以小数，然后将余数替换为原来的大数，将小数替换为原来的余数，直到余数为0为止。此时，用除数就是最大公约数。

下面是辗转相除法的C++代码实现：


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

该代码利用递归的方式实现了辗转相除法，当余数为0时，函数返回除数，即最大公约数。值得一提的是，辗转相除法在数据较大时效率较高。

如果不使用递归来实现辗转相除法，也不会影响其效率，下面是非递归版本的C++代码：


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

当然，除了辗转相除法，更相减损术也可以用于求解最大公约数。代码实现相比辗转相除法略有复杂，而且效率不如辗转相除法，因此这里不作详细介绍。

总之，C++求最大公约数的代码实现已经足够简单，初学者只需掌握其中一种算法，便可应对大多数情况。对于较大的数据，可以考虑使用更高效的算法实现。

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

下一篇: 如何在C++中使用回车符？

()

相似文章