ps：全文圖片均為手繪，如果有不標(biāo)準(zhǔn)的地方還望諒解，之后會慢慢熟悉畫圖工具的，感謝感謝?。?！
1. 輾轉(zhuǎn)相除
歐幾里得算法又稱為輾轉(zhuǎn)相除法，是指用于計算兩個非負(fù)整數(shù)a，b的最大公約數(shù)。
兩個整數(shù)的最大公約數(shù)是指能夠同時整除它們的最大的正整數(shù)。
輾轉(zhuǎn)相除法能夠?qū)崿F(xiàn)效果主要基于以下原理：兩個整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。
原理用用公式表示為：gcd(a,b) = gcd(b,a mod b)。
其中g(shù)cd為最大公約數(shù)的英文greatest common divisor的縮寫
mod相當(dāng)于取模運算符
%
最大公約數(shù)：兩個或多個整數(shù)共有的最大公約數(shù)，用于表示這些整數(shù)之間的最大公共因子。
2. 輾轉(zhuǎn)相除算法的幾何描述
2.1 起源
輾轉(zhuǎn)相除算法起源于希臘，希臘人非常喜歡從圖形或者用幾何的角度去看待問題。希臘數(shù)學(xué)家甚至認(rèn)為，所有的數(shù)字都與一個幾何概念有關(guān)系。所以很自然地，希臘數(shù)學(xué)家在面對求兩個數(shù)的最大公約數(shù)這個問題的時候，首先想到這個問題是否可以轉(zhuǎn)換為一個幾何問題來進(jìn)行處理。在經(jīng)過一些嘗試之后。這一攝像得到實現(xiàn)：將所要求取最大公約數(shù)的兩個數(shù)字a，b分別作為一個矩形的兩條邊，形成一個矩形。
前文提到，兩個整數(shù)共有的最大公約數(shù)，就是用于表示這些整數(shù)之間公共因子中的最大的一個。這是一種偏于數(shù)學(xué)抽象化的描述。那么如何將其進(jìn)行直觀的表示出來呢？也就是如何將最大公約數(shù)問題從用數(shù)字表示，轉(zhuǎn)化為幾何圖形的形式。
即：以需要求取最大公約數(shù)的兩個數(shù)字為邊長，構(gòu)造出一個矩形。然后從這個矩形中尋找出一個小的矩形，或者說一個小的正方形，這個正方形可以沒有縫隙的鋪滿上述構(gòu)造出的矩形。明顯的是這種正方形有很多個，這就像兩個數(shù)字的公因子，可能存在很多個，而我們的任務(wù)就是找出其中最大的那個。
所以我們應(yīng)該怎么找出這個最大的正方形呢？
2.2 鋪瓷磚
不知道大家有沒有看過裝修的時候，工人師傅們鋪瓷磚的場面。
我們是否可以把上述問題想象稱為鋪瓷磚，有一個長為a，寬為b的地面，需要鋪滿瓷磚，需要用多大的正方形瓷磚才能正好將其鋪滿。
如果都用一樣大小的正方形瓷磚，并且這個正方形為其可以選擇的面積最大的正方形，那么鋪瓷磚師傅的工作量將會大大減小吧。
如上圖，所需正方形的變長c便是a和b的約數(shù)，即c為a和b的公約數(shù)，當(dāng)c取到最大值時，即為a和b的最大公約數(shù)。
2.2.1 推導(dǎo)
為了解決上面的問題，我們可以先使用多種尺寸的正方形進(jìn)行填補嘗試，而我們的目的是找到允許存在的最大的正方形，那么我們先從最大面積開始嘗試。
設(shè)寬為a，長為b，其中0<a<b
-
c取a，即正方形面積為a*a
從左往右依次鋪設(shè)變長為a的正方形，發(fā)現(xiàn)地面只能容納兩個，并且剩余一個矩形空間，顯然不符合要求
-
c取a/2，即正方形面積為a/2 * a/2
從左往右依次鋪設(shè)變長為a/2的正方形，發(fā)現(xiàn)地面只能容納8個，并且剩余一個矩形空間，顯然也不符合要求
-
c取a/3，即正方形面積為a/3 * a/3
從左往右依次鋪設(shè)變長為a/3的正方形，發(fā)現(xiàn)地面只能容納18個，并且剩余一個矩形空間，顯然也不符合要求
經(jīng)過三次嘗試，我們發(fā)現(xiàn)總是不能滿足我們的要求，并且每一次右邊都會剩余一部分矩形，對比三張圖片發(fā)現(xiàn)，它們剩余的矩形區(qū)域似乎差不多大小，這是一個新奇的發(fā)現(xiàn)，是否真的如同我們所想，剩余區(qū)域其實是相同大小的矩形呢？我們嘗試著把三個圖形進(jìn)行重疊
上圖為將前三圖重合之后得到，此時我們發(fā)現(xiàn)三個圖不同大小的正方形進(jìn)行填充會存在邊重合的現(xiàn)象，并且每次填充剩余矩形的大小的確為相同的面積。虛線重合地方為綠色加粗線條。
也就是說，無論是使用哪一種大小的正方形進(jìn)行填充，我們都會先把前面綠線前面的以短邊a為面積構(gòu)成的正方形填充掉，剩余一個矩形，那么我們是否可以這樣想？
把以a為邊長的正方形填充的區(qū)域，直接當(dāng)做已經(jīng)填充的區(qū)域，從綠線之后的區(qū)域開始填充。那么此時這個問題就變成了：如何用面積相同的正方形填滿長為a，寬為b-a的長方形呢。此時我們相當(dāng)于簡化了原先的問題。
去除兩個灰色的面積為a*a的正方形，我們得到了一個細(xì)長豎直的長方形，此時短邊為(b-a)，長邊為a
用長邊b / 短邊a 得到的余數(shù)即為c
此時我們設(shè)：c = b%a，即：
此時短邊為c，長邊為a，我們重復(fù)上面的流程，用c為邊長的正方形填充灰色區(qū)域，然后在去掉填充區(qū)域，得到短邊為d，長邊為c的長方形區(qū)域。
用長邊a / 短邊c 得到的余數(shù)即為d
此時設(shè)：d = a%c
此時短邊為d，長邊為c。再次重復(fù)上述流程，用d為邊長的正方形填充灰色區(qū)域。
用長邊c / 短邊d 得到的余數(shù)為0
此時 c%d ==0 即代表不在存在未填充區(qū)域
我們發(fā)現(xiàn)，面積為d*d的正方形正好填充滿這個長方形。
綜上所述，用面積為 d*d 的正方形恰好可以填滿最初面積為 a*b的長方形，這種方式就是輾轉(zhuǎn)相除法
3. 最大公約數(shù)
現(xiàn)在，我們可以嘗試使用輾轉(zhuǎn)相除法，也就是上面貼瓷磚的邏輯，來試求最大公因數(shù)。
例如：我們設(shè)兩個數(shù)，a=6,b=16，求兩個數(shù)的最大公約數(shù)
其中較小者為a，我們用b%a（16%6），得到c=4
此時長邊為6，短邊為4，再用a%c（6%4），得到d=2
此時長邊為4，短邊為2，再用c%2（4%2），得到 0
如此：在最后一步實現(xiàn)了整除，此時除數(shù)也就是短邊為 2 ，這就是6和16的最大公約數(shù)
回顧上述過程，我們發(fā)現(xiàn)其流程與C語言中的函數(shù)，遞歸非常相似，那么我們是否可將其抽象為一個函數(shù)呢？
最大公約數(shù)的英文為：greatest common divisor 取簡稱為gcd
設(shè)函數(shù)名為 gcd，函數(shù)參數(shù)為需要求最大公約數(shù)的兩個整數(shù)，得出 gcd（a,b）；
再次回顧流程，發(fā)現(xiàn)每一次不是用長邊去除短邊，我們可以將每次得到的長邊再次賦值給a，短邊賦值給b，雖然這與前文不同，但是更符合我們的習(xí)慣。長在前，短在后
3.1 算法實現(xiàn)
#include<stdio.h>
int Gcd(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return Gcd(b, a % b);
}
}
int main()
{
int a = 0;
int b = 0;
int ret = 0;
scanf("%d %d", &a, &b);
ret = Gcd(a, b);
printf("%d和%d的最大公約數(shù)是：%d\n", a, b, ret);
return 0;
}
ps：很久都沒有寫過博客了，有些地方講述可能會有些問題，或者模糊。如果有問題，麻煩各位提出，非常感謝。文章來源：http://www.zghlxwxcb.cn/news/detail-788036.html
引用：
輾轉(zhuǎn)相除法介紹
歐幾里得算法文章來源地址http://www.zghlxwxcb.cn/news/detail-788036.html
到了這里，關(guān)于一文看懂什么是歐幾里得算法！多圖演示輾轉(zhuǎn)相除算法究竟是什么！為什么要這樣開展！多圖預(yù)警！的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
