数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用递归查找最大公约数的C++程序
两个数的最大公约数（GCD）是同时能整除这两个数的最大数。
例如：假设我们有以下两个数：45 和 27
63 = 7 * 3 * 3 42 = 7 * 3 * 2 So, the GCD of 63 and 42 is 21
以下是使用递归查找两个数的GCD的程序。
示例
#include<iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
}
int main() {
int a = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}输出
GCD of 63 and 42 is 21
在上面的程序中，gcd() 是一个递归函数。它有两个参数，即 a 和 b。如果 a 或 b 为 0，则函数返回 0。如果 a 和 b 相等，则函数返回 a。如果 a 大于 b，则函数递归调用自身，参数为 a-b 和 b。如果 b 大于 a，则函数递归调用自身，参数为 a 和 b-a。
以下代码片段对此进行了演示。
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
}另一种使用递归查找两个数的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 = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}输出
GCD of 63 and 42 is 21
在上面的程序中，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);
}
更新于：2020年6月24日
9K+ 次浏览
广告