数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时装学
法律研究使用递归欧几里得算法求两个数的最大公约数的 C++ 程序
两个数的最大公约数 (GCD) 是能够同时整除这两个数的最大数。
例如：假设有两个数为 63 和 21。
63 = 7 * 3 * 3 21 = 7 * 3
因此，63 和 21 的 GCD 为 21。
递归欧几里得算法通过使用一对正整数 a 和 b 来计算 GCD，并在 b 为零之前返回 b 和 a%b。
以下是一个使用递归欧几里得算法求两个数的 GCD 的程序 −
示例
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}输出
以上程序的输出如下 −
Enter the values of a and b: 105 30 GCD of 105 and 30 is 15
在以上程序中，gcd() 是一个递归函数。它有两个参数，即 a 和 b。如果 b 等于 0，则将 a 返回到 main() 函数。否则 gcd() 函数使用 b 和 a%b 的值递归调用自身。以下代码片段演示了这一点 −
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}在 main() 函数中，从用户请求 a 和 b 的值。然后调用 gcd() 函数，并显示 a 和 b 的 GCD 值。这在下面可见 −
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}
更新于：2020-06-25
5 千次以上浏览
广告