c語(yǔ)言實(shí)現(xiàn)歐幾里得算法和擴(kuò)展歐幾里得算法

《c語(yǔ)言實(shí)現(xiàn)歐幾里得算法和擴(kuò)展歐幾里得算法》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、1、歐幾里得算法1.1原理闡述歐幾里得算法求最大公約數(shù)原理主要依賴(lài)于以下定理：gcd（a,b）=gcd（b,a%b）。其證明過(guò)程如下：a可以表示成a=kb+r，則r=amodb假設(shè)d是a,b的一個(gè)公約數(shù)，則有d

2、a,d

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

4、r因此d也是（b,amodb）的公約數(shù)因此（a,b）和（b,amodb）的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證。1.2算法設(shè)計(jì)歐幾里得算法通過(guò)對(duì)兩數(shù)進(jìn)行求余，利用gcd（a,b）=gcd（b,a%b）定理不斷反復(fù)循環(huán)，可以得到兩者的最大公約數(shù)。具體流程

5、圖如下：開(kāi)始對(duì)a和b進(jìn)行賦值b=ta=bt=mod（a，b）結(jié)束輸出最大公約數(shù)ba%b=0NY51.3C語(yǔ)言編程實(shí)現(xiàn)以下是C語(yǔ)言程序代碼：#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的最大公約數(shù)，必然存在整數(shù)對(duì)x和y，使得gcd（a，b）=ax+by。2.2算法設(shè)計(jì)開(kāi)始擴(kuò)展歐幾里得算法，精髓在于對(duì)x和y的賦值。對(duì)于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)進(jìn)而可得ay+b(x-a/b*y)=Gcd(a,b)因此對(duì)于a和b而言，他們的相對(duì)應(yīng)的p，q分別是y和(x-a/b*y)。具體流

8、程圖如下：x=ty=x-(a/b)*yt=y結(jié)束輸出最大公約數(shù)a*x+b*yb=0輸入a和b52.3C語(yǔ)言編程實(shí)現(xiàn)以下是C語(yǔ)言程序代碼：#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、，對(duì)12345678和76512348兩數(shù)進(jìn)行最大公約數(shù)的求解中，兩種遞歸算法的迭代次數(shù)都是12次。但是，有所不同的是，在歐幾里得算法中，每次迭代進(jìn)行的操作是對(duì)a和b求余數(shù)。而在擴(kuò)展歐幾里得算法中，每次迭代時(shí)，除了要做一次求商的之外，還要做一次乘法和減法。因此，運(yùn)用歐幾里得算法和擴(kuò)展歐幾里得算法對(duì)兩個(gè)整數(shù)求最大公約數(shù)時(shí)，歐幾里得算法更為高效。5