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

1、1、歐幾里得算法1.1原理闡述歐幾里得算法求最大公約數(shù)原理主要依賴于以下定理：gcd(a,b)=gcd(b,a%b)。其 證明過(guò)程如下：a可以表示成a = kb + r，則r = a mod b假設(shè)d是a,b的一個(gè)公約數(shù)，則有 dla,dlb，而r = a - kb，因此dlr因此d也是(b,a mod b)的公約數(shù)因此(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證。1.2算法設(shè)計(jì)歐幾里得算法通過(guò)對(duì)兩數(shù)進(jìn)行求余，利用gcd (a,b) =gcd (b,a%b)定理不斷反復(fù)循 環(huán)，可以得到兩者的最大公約數(shù)。具體流程圖如下：1.3 C語(yǔ)言編程實(shí)現(xiàn)以下是c語(yǔ)言程序代

2、碼：#includelong 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=%ldn,d);printf(迭代次數(shù)：%ldn,n);return 0;下圖是用V

3、C6運(yùn)行代碼時(shí)的截圖。rI F化常用炊件icrosoft Visual tudioMyProjectsjcDebugXjc.&xeenter the first nunbep:12345678enter the second number：76512348lsfcd=18盲代次數(shù):12Press any key to cont inue2、擴(kuò)展歐幾里得算法2.1原理闡述擴(kuò)展歐幾里德算法是用來(lái)在已知a, b求解一組x和y,使它們滿足等式：ax+by = gcd(a, b) =d(解一定存在，根據(jù)數(shù)論中的相關(guān)定理)。即對(duì)于不完全為0的非負(fù)整數(shù)a，b，gcd (a,b)表示a，b的最大公約數(shù)，必然存

4、在整數(shù)對(duì)x和y，使得gcd(a，b)=ax+by。2.2算法設(shè)計(jì)擴(kuò)展歐幾里得算法，精髓在于對(duì)x和y的賦值。對(duì)于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)進(jìn)而可得 ay +b(x - a / b*y)=Gcd(a,b)因此對(duì)于a和b而言，他們的相對(duì)應(yīng)的p，q分別是y和(x-a/b*y)。具體流程圖如下:開(kāi)始輸入a和bx=ty=x-(a/b)*yt=yb

5、=0輸出最大公約數(shù)a*x+b*y結(jié)束2.3 C語(yǔ)言編程實(shí)現(xiàn)以下是c語(yǔ)言程序代碼：#includelong exEucli(long a,long b,long & x,long & y,long & n)( if(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);print

6、f(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(迭代次數(shù)：%ldn,n);return 0;下圖是在VC6中運(yùn)行代碼時(shí)的截圖。, ”F:常用軟件VC饑Microsoft Visual StudioMyProjertsjcbtnXDebugjcbm.exeenter the irst number： 12345678entep the second numbeF： 76512348 wcd=18倒欹數(shù)：12Press any key to continue3、兩種算法運(yùn)行效率比較通過(guò)對(duì)兩種算法的原理進(jìn)行研究，再結(jié)合以上兩張截圖，我們發(fā)現(xiàn)，對(duì)12345678和 76512348兩數(shù)進(jìn)行最大公約數(shù)的求解中，兩種遞歸算法的迭代次數(shù)都是12次。但是， 有所不同的是，在歐幾里得算法中，每次迭代