---

本文是參考新浪博客而寫。
歐幾里得算法, 又稱輾轉相除法, 用于求兩個自然數的最大公約數. 算法的思想很簡單, 基于下面的數論等式
gcd(a, b) = gcd(b, a mod b)
其中gcd(a, b)表示a和b的最大公約數, mod是模運算, 即求a除以b的余數. 代碼如下:

#include <iostream>
#include <math.h>
using namespace std;int gcd1(int a,int b)//遞歸版本
{if (a<b){int temp=a;a=b;b=temp;}if (b==0){return a;}else{return gcd1(b,a%b);}
}
int gcd2(int a,int b)//循環版本
{if (a<b){int temp=a;a=b;b=temp;}while ( b!=0){int c=a%b;a=b;b=c;}return a;
}
int main()
{int a,b;cout<<"請輸入兩個正數："<<endl;cin>>a>>b;cout<<a<<"與"<<b<<"的最大公約數是:"<<gcd2(a,b)<<endl;//cout<<a<<"與"<<b<<"的最大公約數是:"<<gcd1(a,b)<<endl;}

歐幾里得算法是最古老而經典的算法, 理解和掌握這一算法并不難, 但要分析它的時間復雜度卻并不容易. 我們先不考慮模運算本身的時間復雜度(算術運算的時間復雜度在Knuth的TAOCP中有詳細的討論), 我們只考慮這樣的問題: 歐幾里得算法在最壞情況下所需的模運算次數和輸入的a和b的大小有怎樣的關系?
我們不妨設$a>b\ge1$, 構造數列$\{u_n\}:$

$$u_0=a, u_1=b, ...,u_k=u_{k-2}mod u_{k-1}(k\ge2),$$
顯然, 若算法需要n次模運算, 則有 $u_n=gcd(a, b), u_{n+1}=0$. 我們比較數列 $\{u_n\}$和菲波那契數列 $\{Fn\},$
$$u_n\ge 1=F_0\\ u_{n-1}\ge 1=F_1\\ $$ 又因為由 $u_k mod u_{k+1}=u_{k+2},$可得 $u_k=u_{k+1}\times \beta+u_{k+2} \ge u_{k+1}+u_{k+2}$,故可得 $$u_{n-2}\ge u_{n-1}+u_{n}\ge F_0+F_1=F_2$$ ,以此類推，由數學歸納法容易得到 $$u_{n-k}\ge F_k,$$ 也就是 $$u_k\ge F_{n-k}$$ 于是得到 $a=u_0\ge F_n, b=u_1\ge F_{n-1}$. 也就是說如果歐幾里得算法需要做n次模運算, 則b必定不小于 $F_{n-1}$. 根據斐波那契數列的性質, 有 $$F_{n-1}\gt {(1.618)^n\over \sqrt{5}}$$ , 即 $b\gt {(1.618)^n\over \sqrt{5}}$, 所以模運算的次數為 $O(lgb)$.