最大公约数Greatest Common Divisor(GCD)

时间：2022-02-28 16:58:30

一 暴力枚举法

　　原理：试图寻找一个合适的整数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);
     }
 }

相关文章