Posted on 2010-10-01 13:52
acronix 阅读(227)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题中算法总结
一、最大公倍数
两数的乘积再除以两数的最大公约数法。
这个方法虽然比较复杂,但是使用范围很广。
因为两个数的乘积等于这两个数的最大公约数和最小公倍数的乘积。
例如:4和6的最大公约数是2,最小公倍数是12,那么,4×6=2×12。
为了便于口算,我们可以把两个数中的任意一个数先除以它们的最大公约数,
然后再和另一个数相乘。例如:18和30的最大公约数是6,
要求18和30的最小公倍数时,可以先用18除以6得3,再用3和30相乘得90;
或者先用30除以6得5,再用5和18得90。这90就是18和30的最小公倍数。
二、最大公约数
//辗转相除法--递归
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
//辗转相除法--纯循环
int gcd(int a,int b)
{
int r;
while(b!=0)
{
r=a%b;
a=b;
b=r;
}
return a;
}