java算法（一）欧几里得算法

引言

我是一个1年android开发程序员，工作中遇到的问题不会就百度，再不会就问人，github上开源项目没得，okhttp这样流行的框架也不了解，算法也不会，写的代码自己都不想看。想想自己的确没得什么竞争力，所以决定今年主打俩本书，一本是java数据结构与算法你另外一本是代码的重构。阿里工程师说过一句话:"工程师对于代码，一定要“精益求精”，不论从性能，还是简洁优雅，都要具备“精益求精”的工匠精神，认真打"。这句话深深的对住了我的胃口。对 程序员就要这样。能写出一段高效，简洁，易懂的代码 真的不是容易事。废话不多说了，开始我的算法系列的博客，算是自己给自己的付出记录了一笔。为以后进军大公司做准备。

正题

欧几里得算法定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。
gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)。其中gcd(a,b)表示求a,b间的最大公约数。因此我们只要证明：
gcd(a,b) = gcd(b,a mod b) 那么这个定理就成立.（a>b且b>(a mod b)）
证明过程如下：
设 a=kb+r。那么 r=a%b；r=a-kb。假设d 是a,b公约数。那么d|a,d|b。那么可以知道(a-kb)/d 也是能够除断的。即d|(a-kb)。即d|r。gcd(a,b)公约数为为d。那么d是不是gcd(b,a mod b)的公约数。很显然d也是gcd(b,a mod b)的公约数。说明gcd(a,b)=gcd(b,a mod b)成立。

代码实现：

/**
 * Created by wxy on 2017/5/14.
 * 欧几里得算法
 * 求俩个数的最大公约数
 */
public class FindGcd {
    public long gcd(long n, long n1) {
        while (n1 != 0) {
            long rem = n % n1;
            System.out.println(rem);
            n = n1;
            n1 = rem;
        }
        return n;
    }
    public static void main(String args[]){
        FindGcd findGcd=new FindGcd();
        findGcd.gcd(1989,1590);
        //System.out.println(findGcd.gcd(50,15));
    }
}

时间复杂度：n = O(log(N))

看吧算法的诱惑，假如不知道求最大公约数的算法，靠自己手写代码去解决，想想麻烦还不说，代码执行效率也不高。真正意义上体会到算法的魅力。也体会到数学对编程的帮助。（证明欧几里得算法，看了好几篇文章才懂）。出社会到现在高数老底都被啃光了。以后一边学习算法 一边恶补一下高数，