Posted on 2010-10-01 13:52
acronix 阅读(212)
评论(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;
}