《C语言实现欧几里得算法和扩展欧几里得算法》由会员分享，可在线阅读，更多相关《C语言实现欧几里得算法和扩展欧几里得算法（5页珍藏版）》请在金锄头文库上搜索。
1、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）定理不断反复循环，可以得到两者的最大公约数。具体流程图如下：开始对a和b进行赋值b=ta=bt=mod（a，
2、b）结束输出最大公约数ba%b=0 NY1.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()long a,b,n=0,d,t=0;printf(enter the first number:n);scanf(%ld,&a);printf(enter the second number:n);scanf(%ld,&b);if(ab)t=a;a=b;b=t;d=Eucli(a,b,n);printf(gcd=%
3、ldn,d);printf(迭代次数：%ldn,n);return 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使得 ax + by = Gcd(a,b)由于b
4、 = a% b = a - a / b * b 那么可以得到:ax + by= 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)。具体流程图如下：x=ty=x-(a/b)*yt=y结束输出最大公约数a*x+b*yb=0输入a和b 2.3 C语言编程实现以下是C语言程序代码：#includelong exEucli(long a,long b,long & x,long & y,long & n)if
5、(b = 0) x = 1; y = 0; return a;n+=1;long r = exEucli(b, a%b, x, y,n);long t = y;y = x - (a/b)*y;x = t;return r;int main()long a,b,x,y,n=0,t;printf(enter the first number:n);scanf(%ld,&a);printf(enter the second number:n);scanf(%ld,&b);if(ab)t=a;a=b;b=t;exEucli(a,b,x,y,n);printf(gcd=%ldn,a*x+b*y);printf(迭代次数：%ldn,n);return 0;下图是在VC6中运行代码时的截图。3、 两种算法运行效率比较通过对两种算法的原理进行研究，再结合以上两张截图，我们发现，对12345678和76512348两数进行最大公约数的求解中，两种递归算法的迭代次数都是12次。但是，有所不同的是，在欧几里得算法中，每次迭代进行的操作是对a和b求余数。而在扩展欧几里得算法中，每次迭代时，除了要做一次求商的之外，还要做一次乘法和减法。因此，运用欧几里得算法和扩展欧几里得算法对两个整数求最大公约数时，欧几里得算法更为高效。
