两个正整数的最大公约数(Greatest Common Divisor,GCD)是能够整除这两个整数的最大整数。请实现程序,用递归方法计算两个数的最大公约数。 递归法: 当a > b时,则a 和b与a - b 和 b 的最大公约数相同,即Gcd(a,b)=Gcd(a-b.b) 当b > a时,则a 和b与a 和 b- a 的最大公约数相同,即Gcd(a,b)=Gcd(a.b-a) 当a = b时,a 和 b的最大公约数就是 a (或b) 输入格式: 由用户从键盘输入两个正整数。 输出格式: 输出两个正整数的最大公约数。 如果输入的数不是正整数,则程序输出: Input Data error! 函数接口定义: int Gcd(int a, int b); 其中,a和b是用户输入的两个正整数。 函数返回a和b的最大公约数。 如果a或b不是不是正整数,则函数返回-1。
时间: 2023-06-02 16:07:44 浏览: 163
用递归算法实现两个整数最大公约数的计算
3星 · 编辑精心推荐
抱歉,我可以回答你关于计算两个正整数的最大公约数的问题。下面是递归方法的程序实现:
```
#include <stdio.h>
int Gcd(int a, int b)
{
if (a <= 0 || b <= 0) { // 如果a或b不是正整数,则返回-1
return -1;
}
if (a == b) { // 如果a和b相等,则返回a(或b)
return a;
}
if (a > b) { // 如果a > b,则a 和 b与a - b 和 b 的最大公约数相同
return Gcd(a-b, b);
} else { // 如果b > a,则a 和 b与a 和 b- a 的最大公约数相同
return Gcd(a, b-a);
}
}
int main()
{
int a, b;
printf("请输入两个正整数:");
scanf("%d%d", &a, &b);
int gcd = Gcd(a, b);
if (gcd == -1) {
printf("Input Data error!\n");
} else {
printf("%d和%d的最大公约数为%d\n", a, b, gcd);
}
return 0;
}
```
注意,如果输入的数不是正整数,则会输出 "Input Data error!"。
阅读全文