欧几里得算法---求助--满分相送
对两个非负整数M和N，辗转相除，求它们的最大公约数。那位大哥给出欧几里得算法的递归算法。 问题点数：100、回复次数：3Top
1 楼nemo0228（）回复于 2006-11-01 09:30:51 得分 100
欧几里得算法（Euclid's algorithm，又称辗转相除法）（下文中用gcd(a,b)来表示整数a与b的最大公约数，由于gcd(a,b)=gcd(|a|,|b|)，我们将参数的范围限定在非负整数的范围内）。
将a、b分别分解质因数后即可求得二者的最大公约数，然而即使是最好的算法也不能使位操作意义下的时间复杂度达到多项式级（数论算法的时间复杂度分析常常指在位操作的意义下）。高校的欧几里德算法是建立在下面的定理上的：
对于任何的非负整数a和正整数b,有gcd(a,b)=gcd(b,a mod b)。欧几里得算法的流程为：
EUCLID(a,b)
if b=0
then return a
else return EUCLID(b,a mod b)
比如我们要求31和20的最大公约数,则EUCLID的运行过程为：
EUCLID(30,21)=EUCLID(21,9)=EUCLID(9,3)=EUCLID(3,0)=3。
关于该算法的效率分析，有如下定理阐述：
对任何k>=1，若a>b>=1且b<Fk+1(Fx为Fibonacci数列的第x项)，那么EUCLID(a,b)的递归调用必小于k次。
连续的Fibonacci数是EUCLID输入的最坏情况，因为对任何k>2有Fk+1 mod Fk=Fk-1，所以gcd(Fk+1,Fk)=gcd(Fk,(Fk+1 mod Fk))=gcd(Fk,Fk-1)，而CLID(F3,F2)=EUCLID(2,1)的计算是需要进行一次递归调用的。
现在我们来改写欧几里得算法以计算附加的有用信息，使得我们可以在算法结束时获得两个整数（可能为0或负数）x、y使等式d=gcd(a,b)=ax+by成立。如下所示的EXTENDED-EUCLID过程接收一对非负整数，返回满足上述等式的三元组(d,x,y)：
EXTENDED-EUCLID(a,b)
if b=0
then return (a,1,0)
(d',x',y')←EXTEND-EUCLID(b,a mod b)
(d,x,y)=(d',y',x'-floor(a/b)*y')
return (d,x,y)
EXTENDED-EUCLID过程与EUCLID过程的时间复杂度在渐近意义下相同，差别仅在于常数因子，而由此得出的x、y却对解决一些问题十分有用。
Top
2 楼hdhmail2000（禅剑飞雪）回复于 2006-11-01 17:22:44 得分 0
算法楼上的说了，我就把代码写出来吧：
public class N
{
public int ok(int a,int b)
{
if(b==0)
{
return a;
}
else
{
return ok(b,a%b);
}
}
public static void main(String[] args)
{
if(args.length==2)
{
int a=Integer.parseInt(args[0]);
int b=Integer.parseInt(args[1]);
System.out.println(new N().ok(a,b));
}
}
}Top
3 楼qiuafa（）回复于 2006-11-06 17:34:19 得分 0
template <class T> T gcdw(const T& a, const T& b)
{
const T zero(0);
T m(a), n(b);
while (n!=zero)
{
T r(m%n);
m=n;
n=r;
}
return m;
}
template <class T> T gcdr(const T& a, const T& b)
{
const T zero(0);
if (a==zero && b==zero)
return T(1);
if (a==zero)
return b;
if (b==zero)
return a;
return ((b<a) ? gcdr(b, a) : gcdr(b%a, a));
}
Top
