21xrx.com
2024-12-22 20:41:30 Sunday
登录
文章检索 我的文章 写文章
C++中求最大公约数的方法
2023-07-05 09:56:05 深夜i     --     --
C++ 求最大公约数 方法

在C++中,求两个数的最大公约数有多种方法。在本文中,我们将介绍两种常见的方法:辗转相除法和更相减损法。

辗转相除法

辗转相除法又称欧几里得算法,是求最大公约数的一种基本方法。这个算法基于一条定理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。用数学公式表示为:

gcd(a, b) = gcd(b, a % b), a > b gcd(a, b) = b, a = b

这个算法的思路是,首先确定两个数中较小的数,然后用较大的数除以较小的数,得到余数,然后用较小的数除以余数,得到新的余数。持续这个过程,直到余数等于0,此时上一次的余数即为这两个数的最大公约数。

以下是用辗转相除法求两个数的最大公约数的代码:

int gcd(int a, int b) {

  if (b == 0)

    return a;

   else {

    return gcd(b, a % b);

  }

}

更相减损法

更相减损法是另一种求最大公约数的方法。这个算法的思路是,首先确定两个数中较大的数和较小的数,然后用两个数的差替换较大的数,直到两个数相等,这个数就是这两个数的最大公约数。

以下是用更相减损法求两个数的最大公约数的代码:

int gcd(int a, int b) {

  if (a == b)

    return a;

   else {

    if (a > b) {

      return gcd(a - b, b);

    } else {

      return gcd(a, b - a);

    }

  }

}

总结

两种求最大公约数的方法各有优缺点。辗转相除法的效率较高,但可能会在某些情况下递归太深导致栈溢出。更相减损法的效率较低,但可以避免递归太深导致栈溢出的问题。具体选择哪种方法可以根据不同的情况进行判断。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复