解题思路:
辗转相除法又称为欧几里德算法。这个方法大家已经都已经在数学上学过了。具体的步骤就是:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。最后的除数就是这两个数的最大公约数。举个例子就是:比如两个数字,x=453,y=36;
453%36=21;
36%21=15;
21%15=6;
15%6=3;
6%3=0;
%是取余符号,大家应该都知道吧。所以用这个算法可以求出453和36的最大公约数是3;
注意事项:
参考代码:
#include <stdio.h>
#include <stdlib.h>
//辗转相除
int f(int n, int m)
{
if(m%n==0)return n;
else f(m, n%m);
}
int main()
{
int n, m;
scanf("%d%d",&n, &m);
printf("%d %d\n", f(n, m), n*m/f(n, m));
return 0;
}
0.0分
0 人评分
C语言训练-数字母 (C语言代码)浏览:600 |
2^k进制数 (C语言描述,蓝桥杯)浏览:1418 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:579 |
C语言程序设计教程(第三版)课后习题10.1 (C语言代码)浏览:530 |
第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略浏览:1144 |
1052题解(链表操作)浏览:651 |
班级人数 (C语言代码)浏览:919 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:526 |
C二级辅导-统计字符 (C语言描述——用函数求解)浏览:1156 |
简单的a+b (C语言代码)浏览:596 |