1、1、欧几里得算法1.1原理阐述欧几里得算法求最大公约数原理主要依赖于以下定理：gcd(a,b)=gcd(b,a%b)。其证明过程如下：a可以表示成a=kb+r，则r=amodb假设d是a,b的一个公约数，则有dla,dlb，而r=a-kb，因此dlr因此d也是(b,amodb)的公约数因此(a,b)和(b,amodb)的公约数是一样的，其最大公约数也必然相等，得证。1.2算法设计欧几里得算法通过对两数进行求余，利用gcd(a,b)=gcd(b,a%b)定理不断反复循环，可以得到两者的最大公约数。具体流程图如下：1.3C语言编程实现以下是c语言程序代
2、码：#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:n);scanf(%ld”,&a);printf(enterthesecondnumber:n);scanf(%ld”,&b);if(ab)t=a;a=b;b=t;d=Eucli(a,b,n);printf(gcd=%ldn,d);printf(迭代次数：%ldn,n);return0;下图是用V
4、在整数对x和y，使得gcd(a，b)=ax+by。2.2算法设计扩展欧几里得算法，精髓在于对x和y的赋值。对于a=b,b=a%b而言，我们求得x,y使得ax+by=Gcd(a,b)由于b=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)。具体流程图如下:开始输入a和bx=ty=x-(a/b)*yt=yb
5、=0输出最大公约数a*x+b*y结束2.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;printf(enterthefirstnumber:n);scanf(%ld”,&a);print
6、f(enterthesecondnumber: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);return0;下图是在VC6中运行代码时的截图。,”F:常用软件VC饥MicrosoftVisualStudioMyProjertsjcbtnXDebugjcbm.exeentertheirstnumber：12345678entepthesecondnumbeF：76512348wcd=18倒欹数：12Pressanykeytocontinue3、两种算法运行效率比较通过对两种算法的原理进行研究，再结合以上两张截图，我们发现，对12345678和76512348两数进行最大公约数的求解中，两种递归算法的迭代次数都是12次。但是，有所不同的是，在欧几里得算法中，每次迭代