c语言实现欧几里得算法和扩展欧几里得算法

《c语言实现欧几里得算法和扩展欧几里得算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、欧几里得算法1.1原理阐述欧几里得算法求最大公约数原理主要依赖于以下定理：gcd（a,b）=gcd（b,a%b）。其证明过程如下：a可以表示成a=kb+r，则r=amodb假设d是a,b的一个公约数，则有d

2、a,d

3、b，而r=a-kb，因此d

4、r因此d也是（b,amodb）的公约数因此（a,b）和（b,amodb）的公约数是一样的，其最大公约数也必然相等，得证。1.2算法设计欧几里得算法通过对两数进行求余，利用gcd（a,b）=gcd（b,a%b）定理不断反复循环，可以得到两者的最大公约数。具体流程

5、图如下：开始对a和b进行赋值b=ta=bt=mod（a，b）结束输出最大公约数ba%b=0NY51.3C语言编程实现以下是C语言程序代码：#includelongEucli(longa,longb,long&n){if(b==0)returna;{n=n+1;returnEucli(b,a%b,n);}}intmain(){longa,b,n=0,d,t=0;printf("enterthefirstnumber:");scanf("%ld",&a);printf("enterth

6、esecondnumber:");scanf("%ld",&b);if(a

7、示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)。具体流

8、程图如下：x=ty=x-(a/b)*yt=y结束输出最大公约数a*x+b*yb=0输入a和b52.3C语言编程实现以下是C语言程序代码：#includelongexEucli(longa,longb,long&x,long&y,long&n){if(b==0){x=1;y=0;returna;}n+=1;longr=exEucli(b,a%b,x,y,n);longt=y;y=x-(a/b)*y;x=t;returnr;}intmain(){longa,b,x,y,n=0,t;prin

9、tf("enterthefirstnumber:");scanf("%ld",&a);printf("enterthesecondnumber:");scanf("%ld",&b);if(a

10、，对12345678和76512348两数进行最大公约数的求解中，两种递归算法的迭代次数都是12次。但是，有所不同的是，在欧几里得算法中，每次迭代进行的操作是对a和b求余数。而在扩展欧几里得算法中，每次迭代时，除了要做一次求商的之外，还要做一次乘法和减法。因此，运用欧几里得算法和扩展欧几里得算法对两个整数求最大公约数时，欧几里得算法更为高效。5