- 站点信息
- 问题反馈
- 邮箱：[email protected]
- 吐槽一下
关注微信
©2020-2025 ioDraw All rights reserved,
Privacy Policy
求两个数的最大公约数是生活中常见的运算。我们普遍知道的有欧几里得法、穷举法，其实还有其它方法：更相减损法。下面面一起来看看：
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; }
四种算法各自有自己的优点。