举一个辗转相除法的简单例子
时间: 2023-05-11 07:05:39 浏览: 74
假设我们要求 48 和 18 的最大公约数,可以使用辗转相除法:
48 ÷ 18 = 2 余 12
18 ÷ 12 = 1 余 6
12 ÷ 6 = 2 余 0
因为最后余数为 0,所以 6 是 48 和 18 的最大公约数。
相关问题
举个例子讲讲辗转相除法
辗转相除法是一种求最大公约数的方法。举个例子,假设我们要求 48 和 18 的最大公约数,我们可以用辗转相除法来解决。首先,我们用 48 除以 18,得到商 2 和余数 12。然后,我们用 18 除以 12,得到商 1 和余数 6。接着,我们用 12 除以 6,得到商 2 和余数 0。因为余数为 0,所以我们可以得出 48 和 18 的最大公约数为 6。
c语言 用函数写一个辗转相除法程序
以下是使用函数实现辗转相除法的C语言代码:
```
#include <stdio.h>
int gcd(int a, int b)
{
if (b==0) // 辗转相除法的结束条件
return a;
else
return gcd(b, a%b); // 递归调用辗转相除法
}
int main()
{
int a, b;
printf("请输入两个整数:\n");
scanf("%d%d", &a, &b);
printf("最大公约数是:%d\n", gcd(a, b));
return 0;
}
```
在上述代码中,`gcd()`函数是用来实现辗转相除法的,输入两个整数后,程序将调用`gcd()`函数来计算它们的最大公约数并输出结果。递归调用`gcd()`函数直到`b`等于0,此时返回的`a`就是最大公约数。