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

2023-07-04 17:52:39 深夜i -- --

C++ 最大公约数函数代码

最大公约数是指两个或多个整数的最大公约数，C++中有多种方法可以求出最大公约数，其中较为常用的是利用辗转相除法或欧几里得算法。下面将介绍如何使用C++编写求最大公约数的函数代码。

方法1：辗转相除法

辗转相除法也称作欧几里得算法，是一种辗转相除的方法，用来求两个数的最大公约数。该算法基于这样一个结论：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。下面是使用辗转相除法求最大公约数的函数代码：


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

方法2：欧几里得算法

欧几里得算法，也叫辗转相除法，是一种递归的算法。该算法的计算规则是：用较大数除以较小数，再用除数除以出现的余数（第一余数），再用第一余数除以出现的余数（第二余数），如此反复，直到最后余数是0为止。即：

gcd(a,b) = gcd(b, a mod b)

其中 mod 为取模运算。下面是使用欧几里得算法求最大公约数的函数代码：


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

以上就是两种使用C++编写求最大公约数的函数代码，大家可以根据自己的需求自由选择。

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

下一篇: 如何修改 Dev-C++ 的字体

()

相似文章