原题链接：[编程入门]最大公约数与最小公倍数
解题思路:
利用辗转相除法，求出最大公约数，最小公倍数即为m*n*除于最大公约数。
注意事项:
这里我多写了判断m，n大小，其实这个步骤是没有必要的，大家可以删除if判断试下，理解下为什么f(m,n)跟f(n,m)的结果是相同。加深对辗转相除函数的理解。同时还有个写法是
int f(int m,int n)
{
if(n==0)
return m;
f(n,m%n);
}
这里我就不再修改下列代码，因为根据分析可以想到，我代码中所写的正是上述函数递归的上一步，是等价的。而且减少一个递归更好让人理解。
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include<iostream>#include<cstdio>using namespace std;int f(int m,int n){ if(m%n==0) return n; f(n,m%n);}int main(){ int m,n,x; scanf("%d%d",&m,&n); if(m>n) x=f(m,n); else x=f(n,m); printf("%d ",x); printf("%d",m*n/x); return 0;} |
0 分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复