递归函数)"/>
辗转相除法求最大公约数(递归函数)
辗转相除法,又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它的原理是通过不断地用较小的数去除较大的数,直到两个数相等为止(余数为零),这个相等的数就是它们的最大公约数。
简单来说:1、先用小的一个数除大的一个数,得第一个余数;
2、再用第一个余数除小的一个数,得第二个余数;
3、又用第二个余数除第一个余数,得第三个余数;
4、这样逐次用后一个数去除前一个余数,直到余数是0为止。最后一个除数就是所求的最大公约数。
接下来我们用函数实现:
#include<stdio.h>
int Quto(int x, int y)
{int temp = 0;if (x > y)先判断x和y哪个大 哪个小{temp = x % y;//用大数除以小数得到第一个余数if (temp!= 0)//判断第一个余数是否为零,是的话直接返回y,不是的话返回Quto()函数,继续计算{return Quto(y, temp);}else{return y;}}else //这里是x<y的情况{temp = y % x;if (temp != 0){return Quto(x, temp);}else{return x;}}}
int main()
{int x = 0;int y = 0;int q = 0;printf("输入你想求最大公约数的两个数\n");while (scanf_s("%d%d", &x, &y) != EOF){int q = Quto(x, y);printf("他们的最大公约数为%d\n", q);getchar();}return 0;
}
这就是用递归方法去求最大公约数,递归不太懂的可以去看我第二篇有关递归知识讲解的博客
更多推荐
辗转相除法求最大公约数(递归函数)
发布评论