脚本宝典收集整理的这篇文章主要介绍了【手把手带你刷好题】—— 32.求最大公约数+求最小公倍数,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
目录
方法一:暴力求解
原题二:最小公倍数
方法一:暴力求解
结语
【前言】
今天是刷题打卡第32天!
加油吧少年。
思路:
举一个例子,比如求24和18的最大公约数,它再大,也不可能比18还大,所以先假设最大公约数是18,看18能不能把24和18都整除掉,不能的话就减一,最后就能得到答案,emmm,这个方法很暴力,效率很低,大家简单看一下就行了。
代码执行:
//方法一:暴力求解法
#include<stdio.h>
int main()
{
int m = 0;
int n = 0;
scanf("%d %d", &m, &n);
//求m和n的较小值,假设较小值就是最大公约数
int ret = (m < n) ? (m) : (n);
while (1)
{
if ((m % ret == 0) && (n % ret == 0))
{
break;
}
ret--;
}
PRintf("%dn", ret);
return 0;
}
怎么说呢,当余数等于0的时候,除数就是最大公约数 。有个好处就是不需要判断M和N的大小!
//方法二:辗转相除法
#include<stdio.h>
int main()
{
int m = 0;
int n = 0;
scanf("%d %d", &m, &n);
int ret = 0;
while (ret = m % n)
{
m = n;
n = ret;
}
printf("%dn", n);
return 0;
}
递归实现辗转相除法:
//辗转相除法(递归写法)
#include<stdio.h>
int gcd(int m, int n)
{
if (n == 0)
return m;
return gcd(n, m % n);
}
int main()
{
int m = 0;
int n = 0;
scanf("%d %d", &m, &n);
int ret = gcd(m, n);
printf("%dn", ret);
return 0;
}
思路:
举一个例子,比如求24和18的最小公倍数,它再小,也不可能比24还小,所以先假设最小公倍数是24,看24和18能不能把24整除掉,不能的话就加一,最后就能得到答案,emmm,这个方法很暴力,效率很低,大家简单看一下就行了。
代码执行:
//方法一:暴力求解法
#include<stdio.h>
int main()
{
int m = 0;
int n = 0;
scanf("%d %d", &m, &n);
int ret = (m > n) ? (m) : (n);
while (1)
{
if ((ret % m == 0) && (ret % n == 0))
{
break;
}
ret++;
}
printf("%dn", ret);
return 0;
}
思路:
假如两个数m和n,最大公约数为a,最小公倍数 == m * n / a
代码执行:
//方法二:利用最大公约数
#include<stdio.h>
int gcd(int m, int n)
{
//找递归边界
if (n == 0)
return m;
return gcd(n, m % n);
}
int main()
{
int m = 0;
int n = 0;
scanf("%d %d", &m, &n);
int ret = gcd(m, n);//最大公约数
int s = m * n;
printf("%dn", s / ret);
return 0;
}
今天是刷题打卡第32天!
加油吧少年。
以上是脚本宝典为你收集整理的【手把手带你刷好题】—— 32.求最大公约数+求最小公倍数全部内容,希望文章能够帮你解决【手把手带你刷好题】—— 32.求最大公约数+求最小公倍数所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。