S9T9大都只给公式，然后说了一大堆因为

怼烎@ 2022-08-10 15:50 118阅读 0赞

来源：[S9T9大都只给公式，然后说了一大堆因为][S9T9]

本人S9t9菜鸟一枚，上午在看书的时候突然看到了求最大公约数的一个例题，突然就想到以前好像看过一个欧几里得算法，故又上网仔细找了一下欧几里得算法的原理。可能是本人时间长没看算法，脑子都生锈了。  
看了几个讲解S欧几里得算法的文章，[S9T9][S9T9 1]大都只给公式，然后说了一大堆因为、、、、在我还没看懂的时候，突然来了个所以、、、然后公式就这样推出来的。⊙﹏⊙b汗！  
经过我这令人捉急的小脑袋转了半天，最后有了点眉目，所以拿出来和大家分享一下！  
**1.首先说一下：欧几里得算法是求两个数的最大公约数的，你可能会问：什么是最大公约数？**（⊙﹏⊙我在一开始看到这个问题的时候，我就突然脑子短路，竟然不知道最大公约数是什么了）  
最大公约数：即**能够同时被两个数整除的那个最大的数**。例如：8是16和8的公约数，因为16%8和8%8都等于零嘛！但4也是啊！所以两个数的公约数会有很多，但我们要找出那个最大的！  
  
**2.让我们来使用算式分析一下，假设求x和y的最大公约数。**a).先假设x>y,x和y的最大公约数用f(x,y)表示  
b).假设   x/y = a;  
             x%y = b;  
    所以：a\*y + b = x     
                (这个应该能看出来，因为a为x除以y的整数部分，b为x除以y的余数部分，所以a\*y + b = x)  
   将上面那个式子调换一下位置得到：b = x – a\*y;  
                因为x和y都能够被f(x,y)整除    -----因为f(x,y)是x和y的最大公约数嘛  
                所以 b 也能够被f(x,y)整除      -----即x和y的最大公约数f(x,y),它也是b的约数，所以求x和y的最大公约数也就相当于求y和b的最大公约数。（你可能会问，为什么本来求x和y的最大公约数，最后转了半天变成了求y的b的公约数了？因为 y < x嘛，而且x%y肯定也小于y，所以，这样一来，我们就把求最大公约数的范围缩小了啊）  
所以、欧几里得的公式也就是这么来的f(x,y) = f(y,x%y);  
所以这个算法的实现也就是不停的迭代，直到找出了x%y等于0时，则停止迭代，那个时候最大公约数也就是y了（因为x%y都等于0了，所以x和y的最大公约数也就是y本身了）。  
  
**3.上面可能说得有点啰嗦了，大家莫怪，本人也是想讲得更清楚嘛！下面直接附上代码实现部分：**

> public static int gcd(int x, int y)\{  
>         //防止输入为0，导致程序出错        
>         if(x == 0 || y == 0)\{return 0;\}        
>         //添加一个判断保证x > y        
>         if(x < y)\{        
>             int temp = x;        
>             temp = y;        
>             y = x;        
>         \}        
>         //算法实现        
>         if(x%y == 0)\{        
>             return y;        
>         \}else        
>         \{        
>             return gcd(y,x%y);        
>         \}        
>     \}  
>

其实还有好多其它的优秀的算法，在这里就先不提了，毕竟欧几里得算法就挺高效的。在有些公司，这道题还作为笔试题出现过呢，所以，即将毕业去找工作的未来程序员，还是应该好好看一下的！O(∩\_∩)O哈哈~

[S9T9]: http://www.s9t9.com/thread-5650-1-1.html
[S9T9 1]: http://www.s9t9.com/