题目描述
输入两个整数 a 和 b,请你编写一个函数,int gcd(int a, int b), 计算并输出 a 和 b 的最大公约数。
输入格式
共一行,包含两个整数 a 和 b。
输出格式
共一行,包含一个整数,表示 a 和 b 的最大公约数。
数据范围
1≤a,b≤1000
样例
输入样例:
12 16
输出样例:
4
算法1
系统自带函数gcd(不是鬼吹灯,也不是国产的,这里指最大公约数)
int gcd(int a, int b) // 欧几里得算法
{
return b ? gcd(b, a % b) : a; // 三目运算符
}
这里将三目运算符分解为if语句如下:
int gcd(int a, int b) // 欧几里得算法
{
if(b > 0) return gcd(b, a % b);
else return a;
}
具体的解释如下:
根据题目样例:
12 / 16 = 0 …… 12
//第二步,将原先的除数变到被除数位置,原先的商变到除数的位置
16 / 12 = 1 …… 4
12 / 4 = 3 …… 0
4 / 0 = 0 …… 0 // 此时b(除数)等于0,为false,因此return a
全部的 C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a,b;
int gcd(int a, int b) // 欧几里得算法
{
if(b > 0) return gcd(b, a % b);
else return a;
}
int main()
{
cin>>a>>b;
cout<<gcd(a,b);
return 0;
}
作者写题解不易,给一个赞支持一下呗~