工商銀行一類(lèi)卡限額是多少 _限額

歐幾里得算法是什么？？

文章插圖
歐幾里得算法又稱(chēng)輾轉(zhuǎn)相除法，是指用于計(jì)算兩個(gè)非負(fù)整數(shù)a，b的最大公約數(shù) 。
應(yīng)用領(lǐng)域有數(shù)學(xué)和計(jì)算機(jī)兩個(gè)方面，計(jì)算公式gcd(a,b) = gcd(b,a mod b) 。
歐幾里得算法和擴(kuò)展歐幾里得算法可使用多種編程語(yǔ)言實(shí)現(xiàn) 。
算法簡(jiǎn)介：
歐幾里得算法是用來(lái)求兩個(gè)正整數(shù)最大公約數(shù)的算法。
古希臘數(shù)學(xué)家歐幾里得在其著作《The Elements》中最早描述了這種算法,所以被命名為歐幾里得算法。
擴(kuò)展歐幾里得算法可用于RSA加密等領(lǐng)域。
假如需要求 1997 和 615 兩個(gè)正整數(shù)的最大公約數(shù),用歐幾里得算法，是這樣進(jìn)行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公約數(shù)為1 ，以除數(shù)和余數(shù)反復(fù)做除法運(yùn)算，當(dāng)余數(shù)為 0 時(shí)，取當(dāng)前算式除數(shù)為最大公約數(shù)，所以就得出了 1997 和 615 的最大公約數(shù) 1 。
以上內(nèi)容參考百度百科-歐幾里得算法

文章插圖
The Euclidean Algorithm
歐幾里德算法(又稱(chēng)輾轉(zhuǎn)相除法)是一種用于快速尋找兩個(gè)整數(shù)的最大公約數(shù)的技巧。
最大公約數(shù) Greatest Common Divisor (GCD)：整數(shù) A 和 B 的最大公約數(shù)是指能夠同時(shí)整除 A 和 B 的最大整數(shù) 。
使用歐幾里德算法尋找 GCD(A,B) 的過(guò)程如下：
歐幾里德算法使用了下述特性：
如果 A 和 B 其中一個(gè)為 0，便可利用前兩個(gè)特性得出 GCD 。第三個(gè)特性幫助我們將大而復(fù)雜的問(wèn)題化簡(jiǎn)為小而容易解決的問(wèn)題。歐幾里德算法先利用第三個(gè)特性迅速化簡(jiǎn)問(wèn)題，直至可以通過(guò)前兩個(gè)特性求解為止。
證明 GCD(A,0)=A的過(guò)程如下：
GCD(0,B)=B的證明過(guò)程與此類(lèi)似，區(qū)別僅在于用 B 替換 A 。
先證明較簡(jiǎn)單的 GCD(A,B)=GCD(B,A-B) ，再證明 GCD(A,B)=GCD(B,R)

根據(jù)定義 GCD(A,B) 可均分 A 。因此，A 一定是 GCD(A,B) 的倍數(shù) ，即 X?GCD(A,B)=A ，此處的 X 是某個(gè)整數(shù) 。根據(jù)定義 GCD(A,B) 可均分 B 。因此，B 一定是 GCD(A,B) 的倍數(shù)，即 Y?GCD(A,B)=B ，此處的 Y 是某個(gè)整數(shù) 。
根據(jù) A-B=C 可得出：
由此可見(jiàn) GCD(A,B) 可均分 C 。上圖的左側(cè)部分展示了此證明，提取如下：
證明 GCD(B,C) 均分 A
根據(jù)定義 GCD(B,C) 可均分 B 。因此， B 一定是 GCD(B,C) 的倍數(shù)，即 M?GCD(B,C)=B，此處的 M 是某個(gè)整數(shù) 。根據(jù)定義 GCD(B,C) 可均分 C 。因此，C 一定是 GCD(B,C) 的倍數(shù)，即 N?GCD(B,C)=B，此處的 N 是某個(gè)整數(shù) 。
根據(jù) A-B=C 可得出:
B+C=A
M?GCD(B,C) + N?GCD(B,C) = A
(M + N)?GCD(B,C) = A
由此可見(jiàn) GCD(B,C) 可均分 A 。下圖展示了此證明：
證明 GCD(A,B)=GCD(A,A-B)
根據(jù)定 GCD(A,B) 均分 B
同時(shí)，已證明 GCD(A,B) 均分 C
因此，GCD(A,B) 是 B 和 C 的公約數(shù)
由于 GCD(B,C) 是 B 和 C 的最大公約數(shù)，所以 GCD(A,B) 必須小于或等于 GCD(B,C) 。
根據(jù)定義 GCD(B,C) 均分 B
同時(shí)，已證明 GCD(B,C) 均分 A
因此，GCD(B,C) 是 B 和 A 的公約數(shù)
由于 GCD(A,B) 是 A 和 B 的最大公約數(shù)，所以 GCD(B,C) 必須小于或等于 GCD(A,B) 。
∵ GCD(A,B)≤GCD(B,C) 且 GCD(B,C)≤GCD(A,B) ∴ GCD(A,B)=GCD(B,C) 即 GCD(A,B)=GCD(B,A-B)
下圖的右側(cè)部分展示了此證明的圖示：
前面已證明了 GCD(A,B)=GCD(B,A-B) 另外，對(duì)于 GCD( ) 而言，括號(hào)中各項(xiàng)的順序并不重要，因此 GCD(A,B)=GCD(A-B,B) 那么，如果反復(fù)應(yīng)用 GCD(A,B)=GCD(A-B,B)，便可得到： GCD(A,B)=GCD(A-B,B)=GCD(A-2B,B)=GCD(A-3B,B)=...=GCD(A-Q?B,B) 由于 A= B?Q + R 可得 A-Q?B=R，所以GCD(A,B)=GCD(R,B)。由于括號(hào)中各項(xiàng)的順序并不重要，因此最終可得： GCD(A,B)=GCD(B,R)