C语言实现欧几里得算法和扩展欧几里得算法
1、欧几里得算法
1.1 原理阐述
欧几里得算法求最大公约数原理主要依赖于以下定理：gcd （a,b ）=gcd（b,a%b）。其证明过程如下：a 可以表示成a = kb + r，则r = a mod b假设d 是a,b 的一个公约数，则有d|a,d|b，而r = a - kb，因此d|r因此d 也是（b,a mod b）的公约数因此（a,b ）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证。
1.2 算法设计
欧几里得算法通过对两数进行求余，利用gcd （a,b ）=gcd（b,a%b）定理不断反复循环，可以得到两者的最大公约数。具体流程图如下：
1.3 C语言编程实现
以下是C 语言程序代码：
#include
long Eucli(long a,long b,long &n)
{
if(b==0) return a;
{n=n+1;return Eucli(b,a%b,n);}
}
int main()
{
l ong a,b,n=0,d,t=0;
p rintf("enter the first number:\n");
s canf("%ld",&a);
p rintf("enter the second number:\n");
s canf("%ld",&b);
i f(a
d =Eucli(a,b,n);
p rintf("gcd=%ld\n",d);
p rintf("迭代次数：%ld\n",n);
r eturn 0;
}
下图是用VC6运行代码时的截图。
2、扩展欧几里得算法
2.1 原理阐述
扩展欧几里德算法是用来在已知a, b求解一组x 和y ，使它们满足等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。即对于不完全为 0 的非负整数 a ，b ，gcd （a,b ）表示 a ，b 的最大公约数，必然存在整数对 x 和y ，使得 gcd （a ，b ）=ax+by。
2.2 算法设计
扩展欧几里得算法，精髓在于对x 和y 的赋值。对于a' = b,b' = a % b 而言，我们求得 x,y 使得 a'x + b'y = Gcd(a',b')由于b' = a% b = a - a / b * b 那么可以得到:a'x + b'y=
Gcd(a',b') ，因而bx + (a - a / b * b)，y = Gcd(a',b') = Gcd(a,b)进而可得ay +b(x - a / b*y) = Gcd(a,b)因此对于a 和b 而言，他们的相对应的p ，q 分别是y 和(x-a/b*y)。具体流程图如下：
2.3 C语言编程实现
以下是C 语言程序代码：
#include
long exEucli(long a,long b,long & x,long & y,long & n){
if(b == 0){ x = 1; y = 0; return a;}
n +=1;
l ong r = exEucli(b, a%b, x, y,n);
l ong t = y;y = x - (a/b)*y;x = t;
r eturn r;
}
int main()
{
l ong a,b,x,y,n=0,t;
p rintf("enter the first number:\n");
s canf("%ld",&a);
p rintf("enter the second number:\n");
s canf("%ld",&b);
i f(a
e xEucli(a,b,x,y,n);
p rintf("gcd=%ld\n",a*x+b*y);
p rintf("迭代次数：%ld\n",n);
r eturn 0;
}
下图是在VC6中运行代码时的截图。
3、两种算法运行效率比较
通过对两种算法的原理进行研究，再结合以上两张截图，我们发现，对12345678和76512348两数进行最大公约数的求解中，两种递归算法的迭代次数都是12次。但是，有所不同的是，在欧几里得算法中，每次迭代进行的操作是对a 和b 求余数。而在扩展欧几里得算法中，每次迭代时，除了要做一次求商的之外，还要做一次乘法和减法。因此，运用欧几里得算法和扩展欧几里得算法对两个整数求最大公约数时，欧几里得算法更为高效。