一 暴力枚举法

  原理:试图寻找一个合适的整数i,看看这个整数能否被两个整形参数numberA和numberB同时整除。这个整数i从2开始循环累加,一直累加到numberA和numberB中较小参数的一半为止。循环结束后,上一次寻找到的能够被两整数整除的最大i值,就是两数的最大公约数。

 int getGreatestCommonDivisor(int numberA, int numberB)
 {
      ||numberB < )
     {
         ;
     }

      || numberB <= )
     {
         ;
     }

     int max = numberA > numberB ? numberA : numberB;
     int min = numberA > numberB ? numberB : numberA;

     )
     {
         return min;
     }

     ;
     ;

     ; i <= min/; i++)
     {
         ) && (numberB % i == ))
         {
             ret = i;
         }
     }

     return ret;
 }

二 辗转相除法(欧几里得算法)

  原理:两个正整数a和b(a > b),它们的最大公约数等于a除于b的余数c和b之间的最大公约数。比如10和25,25除以10余数5,那么10和25的最大公约数,等于10和5的最大公约数。然后以此类推,直到两个数可以整除,或者其中一个数减小到1为止。

  缺陷:当两个整形数较大时,a % b取模运算的性能比较低。

 int gcd(int a, int b)
 {
     )
     {
         return b;
     }
     else
     {
         return gcd(b, a%b);
     }
 }

 int getGreatestCommonDivisor(int numberA, int numberB)
 {
      ||numberB < )
     {
         ;
     }

      || numberB <= )
     {
         ;
     }

     int max = numberA > numberB ? numberA : numberB;
     int min = numberA > numberB ? numberB : numberA;

     )
     {
         return min;
     }
     else
     {
         return gcd(max, min);
     }
 }

三 更相减损术

  原理:两个正整数a和b(a > b),它们的最大公约数等于a - b的差值c和较小数b的最大公约数。

  缺陷:更相减损术的运算次数肯定远大于辗转相除法。特别是当两数相差比较大,相减的次数很大。

 int gcd(int a, int b)
 {
     if (a == b)
     {
         return a;
     }

     if (a > b)
     {
         return gcd(a-b, b);
     }
     else
     {
         return gcd(b-a, a);
     }
 }

 int getGreatestCommonDivisor(int numberA, int numberB)
 {
      ||numberB < )
     {
         ;
     }

      || numberB <= )
     {
         ;
     }

     int max = numberA > numberB ? numberA : numberB;
     int min = numberA > numberB ? numberB : numberA;

     )
     {
         return min;
     }
     else
     {
         return gcd(max, min);
     }
 }

四 辗转相除法和更相减损术相结合

  原理:当a和b均为偶数,gcb(a, b) = 2 * gcb(a/2, b/2) = 2 * gcb(a>>1, b>>1) = gcb(a>>1, b>>1) << 1

        当a为偶数,b为奇数,gcb(a, b) = gcb(a/2, b) = gcb(a>>1, b)

     当a为奇数,b为偶数,gcb(a, b) = gcb(a, b/2) = gcb(a, b>>1)

     当a和b均为奇数,先用更相减损术运算一次,gcb(a, b) = gcb(b, a-b),此时a-b是偶数,用上面的公式

  说明:移位运算的性能非常快,a/2 转换成a>>1,a * 2 = a << 1

     和1做&操作,判断奇偶:结果为真奇数,结果为假偶数

 int gcd(int a, int b)
 {
     if (a == b)
     {
         return a;
     }

     )) && (!(b&)))   // a和b均为偶数
     {
         , b>>) << ;
     }
     )) && (b&)) // a偶数,b奇数
     {
         , b);
     }
     ) && (!(b&))) // a奇数,b偶数
     {
         );
     }
     else                        // a和b均为奇数
     {
         if (a > b)
         {
             return gcd(a-b, b);
         }
         else
         {
             return gcd(b-a, a);
         }

         return gcd(a-b, b);
     }
 }

 int getGreatestCommonDivisor(int numberA, int numberB)
 {
      ||numberB < )
     {
         ;
     }

      || numberB <= )
     {
         ;
     }

     int max = numberA > numberB ? numberA : numberB;
     int min = numberA > numberB ? numberB : numberA;

     )
     {
         return min;
     }
     else
     {
         return gcd(max, min);
     }
 }
05-06 20:08