輾轉(zhuǎn)相除法，又稱歐幾里德算法（Euclidean Algorithm），是求兩個(gè)數(shù)的最大公約數(shù)（greatest?common?divisor）的一種方法。用較大的數(shù)除以較小的數(shù)，再以除數(shù)和余數(shù)反復(fù)做除法運(yùn)算，當(dāng)余數(shù)為0時(shí)，取當(dāng)前算式除數(shù)為最大公約數(shù)。
求30和18的最大公約數(shù)：
30 /?18?= 1 余?12
18?/?12?= 1 余?6
12?/? ?6?= 2 余?0
所以，30和18的最大公約數(shù)為6。
如果用小數(shù)除以大數(shù)，只是過程多了一步，結(jié)果沒有差別，所以寫代碼時(shí)不用考慮兩個(gè)數(shù)的大小。
18 /?30?= 0 余?18
30 /?18?= 1 余?12
18?/?12?= 1 余?6
12?/? ?6?= 2 余?0
輾轉(zhuǎn)相除法的原理：
a / b = q 余 r，除數(shù)b和余數(shù)r能被同一個(gè)數(shù)整除，那么被除數(shù)a也能被這個(gè)數(shù)整除?；蛘哒f，除數(shù)與余數(shù)的最大公約數(shù)，就是被除數(shù)與除數(shù)的最大公約數(shù)。即被除數(shù)與除數(shù)的最大公約數(shù)，就是除數(shù)與余數(shù)的最大公約數(shù)。
#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; // 以除數(shù)作為被除數(shù)
n = r; // 以余數(shù)作為除數(shù)
}
printf("%d\n", n); // 最后的除數(shù)為最大公約數(shù)
return 0;
}由于被除數(shù)與除數(shù)的最大公約數(shù)，就是除數(shù)與余數(shù)的最大公約數(shù)，即gcd(a, b) = gcd(b, a%b)，所以也可以設(shè)計(jì)一個(gè)遞歸算法計(jì)算最大公約數(shù)。文章來源：http://www.zghlxwxcb.cn/news/detail-621306.html
#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;
}最小公倍數(shù)是根據(jù)最大公約數(shù)求得的，最小公倍數(shù) = 兩數(shù)乘積 / 最大公約數(shù)。文章來源地址http://www.zghlxwxcb.cn/news/detail-621306.html
到了這里，關(guān)于【算法】輾轉(zhuǎn)相除法求最大公約數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
