Sapphire
2022/2/13
解题思路:
寻找两个数之间的最大公约数,我们所用的方法为辗转相除法(迭代),又称欧几里得算法,具体做法是用较大数除以较小数,再用出现的余数去除以除数,如此反复,直到最后的余数为0为止。
即(m,n)=(n,r)=(r,x),m和n的最大公约数等于n和r的最大公约数也等于r和x的最大公约数,其中r=m%n,x=n%r。意思就是说被除数与除数的最大公约数即是除数与余数的最大公约数,如此迭代下去。
以上算法我们用此语句实现:
int r; while(m%n) { r=m%n; m=n; n=r; } return n;
比如我们输入数字:
m=24,n=18,while(24%18)即while(6)于是执行代码块中语句,r=6,m=18,n=6,下一次时while(m%n)即while(0),所以return 6,6就是两个数字的最大公约数。//(24,18)=(18,6),所以最大公约数为6
m=18,n=24,while(18%24)即while(18)于是执行代码块中语句,r=18,m=24,n=18,也可以把较大数字赋值成为m,较小数字赋值成n。//(18,24)=(24,18)=(18,6),所以最大公约数为6
注意事项:
最小公倍数=两数的乘积/最大公约数
参考代码:
#include<stdio.h> int GCD(int m,int n)//最大公约数 { int r; while(m%n) { r=m%n; m=n; n=r; } return n; } int LCM(int m,int n)//最小公倍数 { return m*n/GCD(m,n); } int main() { int m,n; scanf("%d%d",&m,&n); printf("%d\n",GCD(m,n)); printf("%d",LCM(m,n)); return 0; }
0.0分
12 人评分
简单的a+b (C语言代码)浏览:524 |
C语言训练-求素数问题 (C语言代码)浏览:706 |
C语言训练-计算一个整数N的阶乘 (C语言代码)浏览:895 |
数组输出 (C语言代码)--此题的题目描述有问题浏览:1788 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:509 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:816 |
蚂蚁感冒 (C语言代码)浏览:1294 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:523 |
C语言训练-列出最简真分数序列* (C语言代码)浏览:593 |
老王赛马 (C++代码)浏览:882 |