解题思路:
辗转相除法又称为欧几里德算法。这个方法大家已经都已经在数学上学过了。具体的步骤就是:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是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语言程序设计教程(第三版)课后习题12.3 (C语言代码)浏览:816 |
2006年春浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:789 |
简单的a+b (C语言代码)浏览:547 |
C语言程序设计教程(第三版)课后习题9.1 (Java代码)浏览:467 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:594 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:275 |
本人酷爱递归实现很多问题,这里也是浏览:534 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:619 |
wu-理财计划 (C++代码)浏览:824 |
校门外的树 (C语言代码)浏览:692 |