C++如何求最大公约数 |21xrx.com

C++如何求最大公约数

2023-07-05 06:19:30 深夜i -- --

C++ 最大公约数算法

C++语言是一种高效且广泛应用的编程语言，在实际编程中常常需要使用到最大公约数（Greatest Common Divisor，简称GCD）的计算。下面我们介绍一些常见的C++算法，用于求最大公约数。

1. 辗转相减法

这是一种最简单的算法，思路是不断用较大的数减去较小的数，直到两数相等为止。具体实现如下：


int gcd(int a, int b){
  while(a != b){
    if(a > b) a -= b;
    else b -= a;
  }
  return a;
}

2. 辗转相除法

这种算法是求最大公约数的经典算法，也被称为欧几里德算法（Euclidean algorithm）。它的思路是用较大的数除以较小的数，然后再用除数去除余数，不断重复这个过程，直到余数为0，那么最大公约数就是除数。具体实现如下：


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

3. 更相减损术与移位运算结合法

这种算法是对辗转相减法和辗转相除法的优化，在效率上更高。它的基本思路是将辗转相减法和移位运算结合使用，通过位运算的方式加快计算速度。具体实现如下：


int gcd(int a, int b){
  if(a == b) return a;
  if(a < b) return gcd(b, a);
  if((a & 1) == 0 && (b & 1) == 0) return gcd(a >> 1, b >> 1) << 1;
  else if((a & 1) == 0 && (b & 1) != 0) return gcd(a >> 1, b);
  else if((a & 1) != 0 && (b & 1) == 0) return gcd(a, b >> 1);
  else return gcd(b, a - b);
}

综上所述，C++语言求最大公约数的方法有多种，我们可以根据实际情况选择其中的一种方法。这些算法都有各自的优点和适用场景，我们可以根据不同的需求和数据规模选择不同的算法。

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

下一篇: C++是一种编程语言，属于软件范畴。

评论区

()

相似文章