赞
踩
辗转相除法,又称欧几里德算法(Euclidean Algorithm),是求两个数的最大公约数(greatest common divisor)的一种方法。用较大的数除以较小的数,再以除数和余数反复做除法运算,当余数为0时,取当前算式除数为最大公约数。
求30和18的最大公约数:
30 / 18 = 1 余 12
18 / 12 = 1 余 6
12 / 6 = 2 余 0
所以,30和18的最大公约数为6。
如果用小数除以大数,只是过程多了一步,结果没有差别,所以写代码时不用考虑两个数的大小。
18 / 30 = 0 余 18
30 / 18 = 1 余 12
18 / 12 = 1 余 6
12 / 6 = 2 余 0
辗转相除法的原理:
a / b = q 余 r,除数b和余数r能被同一个数整除,那么被除数a也能被这个数整除。或者说,除数与余数的最大公约数,就是被除数与除数的最大公约数。即被除数与除数的最大公约数,就是除数与余数的最大公约数。
- #include <stdio.h>
-
- int main()
- {
- int m = 0;
- int n = 0;
- scanf("%d %d", &m, &n);
- int r = 0;
- while (r = m % n)
- {
- m = n; // 以除数作为被除数
- n = r; // 以余数作为除数
- }
- printf("%d\n", n); // 最后的除数为最大公约数
- return 0;
- }
由于被除数与除数的最大公约数,就是除数与余数的最大公约数,即gcd(a, b) = gcd(b, a%b),所以也可以设计一个递归算法计算最大公约数。
- #include <stdio.h>
-
- int gcd(int a, int b)
- {
- if (b == 0)
- return a;
- else
- return gcd(b, a % b);
- }
-
- int main()
- {
- int m = 0;
- int n = 0;
- scanf("%d %d", &m, &n);
- printf("%d\n", gcd(m, n));
- return 0;
- }
最小公倍数是根据最大公约数求得的,最小公倍数 = 两数乘积 / 最大公约数。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。