求两个数的最大公约数是生活中常见的运算。我们普遍知道的有欧几里得法、穷举法,其实还有其它方法:更相减损法。下面面一起来看看:
1、辗转相除法,又叫欧几里得法:
int f1(int n1, int m1)//最大公约数子函数 { int n = n1 > m1 ? n1 : m1; int m = n1 < m1
? n1 : m1; if (n % m == 0)//能直接相除的情况 { return m; } else { while (m) { int r = n
% m; n = m; m = r; } return n; } } int main() { printf("输入两个数:\n"); int n=0, m
= 0; scanf("%d%d", &n,& m); int max = f1(n, m); printf("最大公约数是 %d\n", max);
return 0; }
运行结果:
2、递归:
int f1(int n1, int m1)//最大公约数子函数 { int n = n1 > m1 ? n1 : m1; int m = n1 < m1
? n1 : m1; if (n % m == 0)//能直接相除的情况 { return m; } else { return f1(m, n%m); }
} int main() { printf("输入两个数:\n"); int n=0, m = 0; scanf("%d%d", &n,& m); int
max = f1(n, m); printf("最大公约数是 %d\n", max); return 0; }
运行结果:
3、更相减损法:
int f1(int n1, int m1)//最大公约数子函数 { int n = n1 > m1 ? n1 : m1; int m = n1 < m1
? n1 : m1; if (n % m == 0) return m; else { return f1(m, n - m); } } int main()
{ printf("输入两个数:\n"); int n=0, m = 0; scanf("%d%d", &n,& m); int max = f1(n,
m); printf("最大公约数是 %d\n", max); return 0; }
运行结果:
4、穷举法:
int f1(int n1, int m1)//最大公约数子函数 { int n = n1 > m1 ? n1 : m1; int m = n1 < m1
? n1 : m1; int i = 0; for (i=m; i >= 1; i--) { if (n % i == 0 && m % i == 0) {
return i; break; } } return 1; } int main() { printf("输入两个数:\n"); int n=0, m =
0; scanf("%d%d", &n,& m); int max = f1(n, m); printf("最大公约数是 %d\n", max);
return 0; }
四种算法各自有自己的优点。