C++算法：最大公约数 |21xrx.com

2023-07-05 07:33:57 深夜i -- --

C++ 算法最大公约数 GCD 辗转相除法

最大公约数可以用于很多问题，例如化简分数、判断两个数是否互质等等。在C++中，我们可以使用递归和非递归两种方法来求两个数的最大公约数。

1. 递归法：

递归算法的基本思想是将原问题转化为更小的相似的子问题，并通过递归调用自身来解决问题，直到子问题无法再分解为止，最后将结果合并得到原问题的解。

求最大公约数的递归算法如下：

int gcd(int a, int b) {

if (b == 0) return a;

return gcd(b, a % b);

}

2. 非递归法：

非递归算法的基本思想是使用循环迭代处理问题，通过每次处理一个较小的子问题来得到最终的解。

求最大公约数的非递归算法如下：

int gcd(int a, int b) {

while (b != 0)

int temp = a % b;

a = b;

b = temp;

return a;

}

以上两种方法都是基于欧几里得算法的，其正确性和时间复杂度都是O(logn)。

可以看出，使用C++求最大公约数是非常简单的。无论是递归还是非递归，其实现都非常直观。在应用中，我们可以灵活地选择使用哪种方法来求解问题，以达到较好的效果。

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

下一篇: C++如何输出数字的最小位数？

()

相似文章