Go语言视频零基础入门到精通

javalearner

[blockquote]
    辗转相除法是用于求两个数的最大公约数的方法。
   [/blockquote]       首先解释下什么是最大公约数（相信很多人都清楚了）：若整数a能被整数k（k≠0）整除，则称k为a的约数。如果k既是a的约数，又是b的约数，则k称为a和b的公约数。a和b可以有多个公约数，其中最大的一个公约数称为最大公约数。 辗转相除法的步骤是：
   [blockquote]
    （1） 用两个数中的大数除以小数，得到余数。
   [/blockquote]        （2） 以（1）中的小数替换（1）中的大数，以（1）中的余数替换（1）中的小数，返回（1）。
   [blockquote]
    直到当小数为0，这时的大数即为最大公约数。
   [/blockquote] 证明： 设
欲证
先设
   
   
   
     
    由 可得且知
表示d是b,r的公因数，但
所以

可得且知
表示e是a,b的公因数，但[url=http://images.cnblogs.com/cnblogs_com/icescut/WindowsLiveWriter/507bb7ffe718_8749/clip_image003[1].gif][/url]
所以
由可得知
代码实现：  
   
     
    //
    求最大公约数
   

    public
     
    class
     GcdTest{
     
    //
    递归
   

        
    public
     
    static
     
    int
     gcd(
    int
     a,
    int
     b) {
         
    if
    ( b
    ==
     
    0
    ) {
            
    return
     a;
         }
    else
     {
            
    return
     gcd(b, a
    %
     b);
         }
     }

     
    //
    迭代   
   

        
    public
     
    static
     
    int
     gcd2(
    int
     a,
    int
     b) {
         
    int
     r;
         
    while
    ( b
    !=
     
    0
    ) {
             r
    =
     a
    %
     b;
             a
    =
     b;
             b
    =
     r;
         }
         
    return
     a;
     }
     
     
    public
     
    static
     
    void
     main(String[] args){
         
    int
     res;
         res
    =
     gcd(
    32
    ,
    4
    );
         System.out.println(res);
         res
    =
     gcd2(
    24
    ,
    16
    );
         System.out.println(res);
     }
}

     
   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/13/000605015.zip