C++最大公约数（递归）详解
发布时间：2020-12-16 07:37:14 所属栏目：百科 来源：网络整理
导读：使用递归可以计算两个数字的最大公约数。根据欧几里得算法，两个正整数 x 和 y 的最大公约数的计算方法如下: gcd(x，y) = y; 如果y除以x而没有余数 gcd(x，y) = gcd(y,x/y的余数)；否则 这个定义指出，如果 x/y 没有余数，则 x 和 y 的最大公约数是 y；否则，
|
使用递归可以计算两个数字的最大公约数。根据欧几里得算法，两个正整数 x 和 y 的最大公约数的计算方法如下:
gcd(x，y) = y; 如果y除以x而没有余数 下面的程序显示了递归的 C++ 实现：
// This program demonstrates a recursive function to
// calculate the greatest common divisor (gcd) of two numbers.
#include <iostream>
using namespace std;
// Function prototype
int gcd(int,int);
int main()
{
int num1,num2;
cout << "Enter two integers: ";
cin >> num1 >> num2;
cout << "The greatest common divisor of " << num1;
cout << " and " << num2 << " is ";
cout << gcd(num1,num2) << endl;
return 0;
}
int gcd(int x,int y)
{
if (x % y == 0) //base case
return y;
else
return gcd{y,x % y);
}
程序输出结果：
Enter two integers: 49 28 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |