C++中实现求最大公约数函数gcd |21xrx.com

C++中实现求最大公约数函数gcd

2023-06-29 01:10:51 深夜i -- --

C++ 最大公约数函数实现 gcd

在 C++ 中，求最大公约数是一个基础算法。最大公约数（Greatest Common Divisor，简称 GCD）指的是多个数中最大的公约数，也就是能够同时整除这些数的最大自然数。

在 C++ 中，可以使用欧几里得算法（Euclidean Algorithm）来求解最大公约数。欧几里得算法原理是：两个数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

下面是实现求最大公约数的 C++ 函数 gcd：


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

这个函数接受两个参数 a 和 b，返回它们的最大公约数。

函数体中使用了递归。如果 b 为 0，直接返回 a，因为此时 a 就是最大公约数。否则，继续递归，将 b 和 a 除以 b 的余数作为新的 a 和 b，继续计算它们的最大公约数。

例子：


int main() {
  cout << gcd(10, 25) << endl; // 输出 5
  cout << gcd(12, 18) << endl; // 输出 6
  cout << gcd(24, 60) << endl; // 输出 12
  return 0;
}

当然，C++ 也提供了 math 库，可以使用其中的 gcd 函数（需要包含头文件）：


#include <iostream>
#include <numeric>
using namespace std;
int main() {
  cout << gcd(10, 25) << endl; // 输出 5
  cout << gcd(12, 18) << endl; // 输出 6
  cout << gcd(24, 60) << endl; // 输出 12
  return 0;
}

以上是 C++ 中实现求最大公约数函数 gcd 的方法及例子。在实际编程中，可以根据需要选择其中的一种方法来求解最大公约数。

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

下一篇: C++11线程锁简介

评论区

()

相似文章