C++求最大公约数的方法 |21xrx.com

C++求最大公约数的方法

2023-06-30 16:04:36 深夜i -- --

C++ 最大公约数方法

C++是一种流行的编程语言，被广泛应用于各种领域，包括数学和算法。在程序设计中，求最大公约数是一个非常常见的问题。本文将介绍使用C++求最大公约数的几种方法。

1. 暴力枚举法

暴力枚举法是最简单的方法，也是最慢的方法。该方法从较小的数开始逐个尝试，直到找到两个数的公约数或者两个数都被尝试过为止。代码如下：


int gcd(int a, int b) {
  int res = 0;
  for(int i = 1; i <= min(a,b); i++) {
    if(a%i == 0 && b%i == 0)
      res = i;
  } 
  return res;
}

2. 辗转相除法

辗转相除法（欧几里得算法）是一种更高效的方法。该方法基于以下原理：若a>b，则a和b的最大公约数等于b和a%b的最大公约数。代码如下：


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

3. Stein算法

Stein算法是一种快速求最大公约数的算法，它比辗转相除法更快。该算法的原理是：如果a和b都是偶数，则gcd(a,b)=2\*gcd(a/2,b/2)；如果只有一个是偶数，则gcd(a,b)=gcd(a/2,b)或gcd(a,b/2)；如果都是奇数，则gcd(a,b)=gcd(|a-b|/2,b)，其中||表示取绝对值。代码如下：


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

在实际编程中，要根据具体情况选择合适的算法。上述三种方法都可以求解最大公约数，但是它们的效率不同，应根据实际情况进行选择。

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

下一篇: 下使用最方便？

评论区

()

相似文章