欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
我们来用实际题目来探讨：如何求10和6的最大公约数？
1.将两数相除，求余数。10/6=1······4。
2.将除数和余数再进行求余运算。 6/4=1······2。
3.重复第二步直到余数为0。4/2=2······0 当余数为0时，被除数即为10和6的最大公约数。得出答案，10和6的最大公约数为2。
有了上述实现过程，那我们就可以用代码实现一遍了。上代码
public int gcd(int p, int q) {
if (q == 0) return p;//直到除数为0，那么我们就知道被除数就是我们要的答案了
int r = p % q;
return gcd(q, r);
}
算法的复杂度我不会分析，看别人的解释我也看不懂，可能是我数学底子太差，有兴趣的可以自行研究下。
例1：有两个容器A、B分别能装3升和5升水，还有个足够大的容器C，问能否往C中精确到出14升水？（仅能精确倒A3升，B5升，B装满5升之后倒出3升给A剩下2升，这是允许的操作）
分析题目可知我们可以倒的水为3升、5升、2升。列方程 3x+5y+2z=14。当存在xyz系数为整数等式成立的情况下就能倒出14升水！
我们暴力破解将数字一个一个代入进入
就能知道 2次5升加2次2升就能得到14升水。
例2：接下来要用算法实现，任意容积的A，任意B，能否精确到出C升水？其中 0<A<B
设X1次A，X2次B，X3次（B-A）能够倒出C升水。
列方程：X1A+X2B+X3(B-A)=C X1X2X3为整数时，则能够准确倒出C升水。
化简方程：(X1-X3)A+(X2+X3)*B=C
设x=X1-X3 y=X2+X3 得：
xA+yB=C
假设x、y为正整数，我们用几个for循环暴力破解就能得到答案了，有没有更好的办法呢？答案肯定是有的，算法就是为了加速得出结果而生的。
扩展的欧几里德算法:
对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by.
根据欧几里德扩展算法，Gcd(A, B) = Ax + By，x和y均为整数。求出A和B的最大公约数，如果C能被最大公约数整除Gcd(A, B) 整除，那就可以实现水缸里恰好为C升水； 那题目就直接转换为求A 、B的最大公约数了。
上述题目直接变成了：C如果能够被ab的最大公约数整除，答案则为能；不能整除，答案为不能。
上代码：
public static Boolean can(int a, int b, int c) {
//求出ab的最大公约数
int gcd = gcd(a, b);
if (0 == c % gcd)
return true;
return false;
}
测试结果:
a=3 b=5 c=14,result=true
a=123 b=456 c=6543213,result=true
a=2 b=1000 c=1001,result=false
以上就是欧几里得算法的体现。
抛砖引玉，留下一个题：在平面上有一个两端无限延伸的数组如下图所示，0为起点，1是终点，现在你有四种走法，向正方向走a步，向负方向走a步，向正方向走b步，向负方向走b步。可以随便走多少次都可以！在任给两个数a,b问能否从起点走到终点。如图1
本系列所有的代码都会在github同步更新，立刻前往
