Algorithms.Euclid(歐幾里得演算法）

對最大公約數問題的求解演算法——歐幾里得演算法由於其很好的體現了演算法精確，輸出，有窮性等特性被用在很多演算法設計分析書籍的開篇第一個例子，但多數都只是簡單的對求解步驟用編程語言進行了複述而已，很少有人去向讀者解釋原理（雖然這也許不屬於演算法內容），本著知其然也要知其所以然的原則，接下來我將通過「正確性」，和「有窮性」兩個方面來證明歐幾里得演算法。

首先我們來看一個確切的例子：用歐幾里得演算法求158和44的最大公約數；

158=44*3+26；44=26*1+18；26=18*1+8；18=8*2+2；8=2*4+0;

得158和44的最大公約數為2. 接下來我們將其抽象：求正整數a>b得最大公約數。（鍵盤寫公式麻煩，貼上手寫過程）

圖1.

1.那麼我們如何來證明rn就是a和b得最大公約數呢？還是貼上手寫證明過程。(需要大家注意一下：若有兩個正整數m,n，我們一般將m整除n表示為m|n.)

圖2.

因此得證rn是a,b得公約數。

2.怎樣證明其是最大公約數呢？

圖3.

3.最後肯定會有人問，如何確定最終餘數一定為零呢？（即如何確定其有窮性呢）

圖4.

至此我們以證明開篇得兩個問題，即證明了歐幾里得演算法。

最後附上其代碼實現

//Eculid(m,n)//使用歐幾里得演算法計算gcd(m,n)//輸入兩個不全為0得非負數整數m,n,輸出m,n得最大公約數#include <stdio.h>void Eculid(int m,int n){ int r; while(n!=0){ r=m%n; m=n; n=r; } printf("%d",m);}int main(){ int a,b; scanf("%d,%d",&a,&b); Eculid (a,b); return 0;}

推薦閱讀：