算法01-欧几里得算法

前言：

从事计算机行业，如果不懂算法，那么很难使自己的技术水平有一个质的提升，自觉自己的算法基础比较薄弱，因此开此篇算法100篇系列，以督促自己在程序猿的道路上越走越远😝！

正文：

既然是开篇，俗话说万事开头难，笔者就先来个简单点的吧。

欧几里得算法：

自然语言描述：

计算两个非负整数p和q的最大公约数：若q是0，则最大公约数为p。否则，将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数。

C语言实现：

int gcd(int p,int q){
    if (0==q) {
        return p;
    }
    int r = p%q;
    return gcd(q, r);
}

欧几里德算法的思想：

辗转相除法是欧几里德算法的核心思想，欧几里德算法说白了其实就是辗转相除法的计算机算法的实现而已。下面我们先说说辗转相除法，辗转相除法的内容：如果用gcd(a,b)来表示a和b的最大公约数，那么根据辗转相除法的原理，有gcd(a,b)=gcd(a,a mod (b))，其中mod()表示模运算，用C语言表示模运算a%b,即a除以b取余，并且不妨让a>b,这样方便于模运算。

辗转相除法的正确性gcd(a,b)=gcd(a,a mod (b))的证明：

First：令c为a和b的最大公约数，数学符号表示为c=gcd(a,b)。因为任何两个实数的最大公约数c一定是存在的，也就是说必然存在两个数k1,k2使得a=k1*c, b=k2*c；
Second：a mod (b)等价于存在整数r,k3使得余数r=a – k3*b；
即r = a – k3*b
      = k1*c – k3*k2*c
      = (k1 – k3*k2)*c
显然，a和b的余数r是最大公约数c的倍数！

结语：

此篇为算法100篇系列的第一篇，后续会有陆续的篇章推出，由易到难循序渐进，共同加油，欧耶✌️！
未完待续...

不积跬步，无以至千里；不积小流，无以成江海。