求两个正整数 x,y 的最大公约数。 设计一个递归算法,求解两个正整数 x,y 的最大公约数。给出代码
时间: 2024-01-22 15:21:38 浏览: 49
最大公约数也叫最大公因数,可以使用辗转相除法求解。递归算法的实现如下:
```
int gcd(int x, int y) {
if (x % y == 0) {
return y;
} else {
return gcd(y, x % y);
}
}
```
其中,当 y 能够整除 x 时,y 就是最大公约数;否则,继续递归调用 gcd 函数,将 y 和 x % y 传入,直到 y 能够整除 x。
完整代码如下:
```c++
#include <iostream>
using namespace std;
int gcd(int x, int y) {
if (x % y == 0) {
return y;
} else {
return gcd(y, x % y);
}
}
int main() {
int x, y;
cout << "请输入两个正整数:";
cin >> x >> y;
cout << "它们的最大公约数是:" << gcd(x, y) << endl;
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)