C++算法：辗转相除法求最大公约数 |21xrx.com

2023-07-06 19:59:43 深夜i -- --

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

在数学中，最大公约数是指两个或多个整数的公共因子中最大的一个。C++语言中，我们可以使用辗转相除法来求解最大公约数。

辗转相除法，也称欧几里得算法，是一种求最大公约数的有效方法。其基本思想是，两个整数的最大公约数即为其中较小的数和两数之差的最大公约数，如此递归下去，直到两数相等时停止。具体而言，假设两个数为a和b，其中a>b，则有：

a = b * q + r

其中q和r分别为a除以b所得商和余数，如果r为0，则b即为最大公约数；否则，以b和r继续递归求解，即：

gcd(a,b) = gcd(b,r)

接下来，我们就使用C++语言实现辗转相除法求最大公约数的过程。

首先，我们需要引入头文件：

#include

using namespace std;

接下来，我们可以定义一个函数来实现辗转相除法求最大公约数，代码如下：

int gcd(int a, int b)

{

if(b == 0)

return a;

else

return gcd(b, a % b);

}

在上面的代码中，我们使用递归来实现辗转相除法求最大公约数。如果b等于0，则a即为最大公约数；否则，继续以b和a除以b所得的余数来递归求解。

最后，我们可以在主函数中调用上面定义的函数，输入两个整数并输出它们的最大公约数：

int main()

{

int a, b, result;

cout<<"请输入两个整数："<

cin>>a>>b;

result = gcd(a, b);

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

下一篇: C++字符集简介

()

相似文章