数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序查找最大公约数
两个数的最大公约数 (GCD) 是可以同时整除这两个数的最大数。
例如：假设我们有两个数 45 和 27。
45 = 5 * 3 * 3 27 = 3 * 3 * 3
那么，45 和 27 的最大公约数是 9。
查找两个数的最大公约数的程序如下所示。
示例
#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 = 105, b = 30;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}输出
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);
}另一个查找两个数的最大公约数的程序如下所示：
示例
#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 = 105, b =30;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}输出
GCD of 105 and 30 is 15
在上面的程序中，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);
}
更新于： 2020年6月24日
14K+ 浏览量
广告