جافا: احصل على أعظم مقسوم مشترك

Question

لقد رأيت أن هذه الوظيفة موجودة BigInteger, ، بمعنى آخر BigInteger#gcd. هل هناك وظائف أخرى في Java تعمل أيضًا على أنواع أخرى (int, long أو Integer))؟ يبدو أن هذا سيكون منطقيًا java.lang.Math.gcd (مع جميع أنواع الحمولة الزائدة) لكنها ليست موجودة. هل هو مكان آخر؟

---

(لا تخلط بين هذا السؤال و "كيف يمكنني تنفيذ هذا بنفسي" ، من فضلك!)

Answer 1

ل int وطويلة ، مثل البدائية ، وليس حقا. بالنسبة إلى عدد صحيح ، من الممكن أن يقوم شخص ما بكتابة واحدة.

بالنظر إلى أن BigInteger عبارة عن مجموعة Superset (الرياضية/الوظيفية) من int و integer وطويلة وطويلة ، إذا كنت بحاجة إلى استخدام هذه الأنواع ، وتحويلها إلى biginteger ، والقيام GCD ، وتحويل النتيجة مرة أخرى.

private static int gcdThing(int a, int b) {
    BigInteger b1 = BigInteger.valueOf(a);
    BigInteger b2 = BigInteger.valueOf(b);
    BigInteger gcd = b1.gcd(b2);
    return gcd.intValue();
}

Answer 2

على حد علمي ، لا يوجد أي طريقة مدمجة للبدائل. لكن شيئًا بسيطًا مثل هذا يجب أن يفعل الخدعة:

public int GCD(int a, int b) {
   if (b==0) return a;
   return GCD(b,a%b);
}

يمكنك أيضًا خط واحد إذا كنت في هذا النوع من الأشياء:

public int GCD(int a, int b) { return b==0 ? a : GCD(b, a%b); }

تجدر الإشارة إلى أن هناك بالتأكيد لا الفرق بين الاثنين لأنها تجمع إلى نفس رمز البايت.

Answer 3

أو خوارزمية الإقليدية لحساب GCD ...

public int egcd(int a, int b) {
    if (a == 0)
        return b;

    while (b != 0) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }

    return a;
}

Answer 4

استخدم الجوافة LongMath.gcd() و IntMath.gcd()

Answer 5

Jakarta Commons Math لديه ذلك بالضبط.

الحساب

Answer 6

ما لم يكن لدي جوافة ، أعرّف هكذا:

int gcd(int a, int b) {
  return a == 0 ? b : gcd(b % a, a);
}

Answer 7

يمكنك استخدام هذا التنفيذ خوارزمية GCD الثنائية

public class BinaryGCD {

public static int gcd(int p, int q) {
    if (q == 0) return p;
    if (p == 0) return q;

    // p and q even
    if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;

    // p is even, q is odd
    else if ((p & 1) == 0) return gcd(p >> 1, q);

    // p is odd, q is even
    else if ((q & 1) == 0) return gcd(p, q >> 1);

    // p and q odd, p >= q
    else if (p >= q) return gcd((p-q) >> 1, q);

    // p and q odd, p < q
    else return gcd(p, (q-p) >> 1);
}

public static void main(String[] args) {
    int p = Integer.parseInt(args[0]);
    int q = Integer.parseInt(args[1]);
    System.out.println("gcd(" + p + ", " + q + ") = " + gcd(p, q));
}

}

من عند http://introcs.cs.princeton.edu/java/23recursion/binarygcd.java.html

Answer 8

بعض التطبيقات هنا لا تعمل بشكل صحيح إذا كان كلا الرقمين سلبيين. GCD (-12 ، -18) هو 6 ، وليس -6.

لذلك يجب إرجاع القيمة المطلقة ، شيء مثل

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

Answer 9

يمكننا استخدام الوظيفة العودية للعثور على GCD

public class Test
{
 static int gcd(int a, int b)
    {
        // Everything divides 0 
        if (a == 0 || b == 0)
           return 0;

        // base case
        if (a == b)
            return a;

        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }

    // Driver method
    public static void main(String[] args) 
    {
        int a = 98, b = 56;
        System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
    }
}

Answer 10

إذا كنت تستخدم Java 1.5 أو لاحقًا ، فهذه خوارزمية GCD ثنائية تكرارية تستخدم Integer.numberOfTrailingZeros() لتقليل عدد الشيكات والتكرار المطلوب.

public class Utils {
    public static final int gcd( int a, int b ){
        // Deal with the degenerate case where values are Integer.MIN_VALUE
        // since -Integer.MIN_VALUE = Integer.MAX_VALUE+1
        if ( a == Integer.MIN_VALUE )
        {
            if ( b == Integer.MIN_VALUE )
                throw new IllegalArgumentException( "gcd() is greater than Integer.MAX_VALUE" );
            return 1 << Integer.numberOfTrailingZeros( Math.abs(b) );
        }
        if ( b == Integer.MIN_VALUE )
            return 1 << Integer.numberOfTrailingZeros( Math.abs(a) );

        a = Math.abs(a);
        b = Math.abs(b);
        if ( a == 0 ) return b;
        if ( b == 0 ) return a;
        int factorsOfTwoInA = Integer.numberOfTrailingZeros(a),
            factorsOfTwoInB = Integer.numberOfTrailingZeros(b),
            commonFactorsOfTwo = Math.min(factorsOfTwoInA,factorsOfTwoInB);
        a >>= factorsOfTwoInA;
        b >>= factorsOfTwoInB;
        while(a != b){
            if ( a > b ) {
                a = (a - b);
                a >>= Integer.numberOfTrailingZeros( a );
            } else {
                b = (b - a);
                b >>= Integer.numberOfTrailingZeros( b );
            }
        }
        return a << commonFactorsOfTwo;
    }
}

اختبار الوحدة:

import java.math.BigInteger;
import org.junit.Test;
import static org.junit.Assert.*;

public class UtilsTest {
    @Test
    public void gcdUpToOneThousand(){
        for ( int x = -1000; x <= 1000; ++x )
            for ( int y = -1000; y <= 1000; ++y )
            {
                int gcd = Utils.gcd(x, y);
                int expected = BigInteger.valueOf(x).gcd(BigInteger.valueOf(y)).intValue();
                assertEquals( expected, gcd );
            }
    }

    @Test
    public void gcdMinValue(){
        for ( int x = 0; x < Integer.SIZE-1; x++ ){
            int gcd = Utils.gcd(Integer.MIN_VALUE,1<<x);
            int expected = BigInteger.valueOf(Integer.MIN_VALUE).gcd(BigInteger.valueOf(1<<x)).intValue();
            assertEquals( expected, gcd );
        }
    }
}

Answer 11

public int gcd(int num1, int num2) { 
    int max = Math.abs(num1);
    int min = Math.abs(num2);

    while (max > 0) {
        if (max < min) {
            int x = max;
            max = min;
            min = x;
        }
        max %= min;
    }

    return min;
}

تستخدم هذه الطريقة خوارزمية Euclid للحصول على "أعظم مقسوم مشترك" من اثنين من الأعداد الصحيحة. يستقبل اثنين من الأعداد الصحيحة ويعيد GCD منهم. هذا سهل!

Answer 12

/*
import scanner and instantiate scanner class;
declare your method with two parameters
declare a third variable;
set condition;
swap the parameter values if condition is met;
set second conditon based on result of first condition;
divide and assign remainder to the third variable;
swap the result;
in the main method, allow for user input;
Call the method;

*/
public class gcf {
    public static void main (String[]args){//start of main method
        Scanner input = new Scanner (System.in);//allow for user input
        System.out.println("Please enter the first integer: ");//prompt
        int a = input.nextInt();//initial user input
        System.out.println("Please enter a second interger: ");//prompt
        int b = input.nextInt();//second user input


       Divide(a,b);//call method
    }
   public static void Divide(int a, int b) {//start of your method

    int temp;
    // making a greater than b
    if (b > a) {
         temp = a;
         a = b;
         b = temp;
    }

    while (b !=0) {
        // gcd of b and a%b
        temp = a%b;
        // always make a greater than b
        a =b;
        b =temp;

    }
    System.out.println(a);//print to console
  }
}

Answer 13

لقد استخدمت هذه الطريقة التي أنشأتها عندما كان عمري 14 عامًا.

    public static int gcd (int a, int b) {
        int s = 1;
        int ia = Math.abs(a);//<-- turns to absolute value
        int ib = Math.abs(b);
        if (a == b) {
            s = a;
        }else {
            while (ib != ia) {
                if (ib > ia) {
                    s = ib - ia;
                    ib = s;
                }else { 
                    s = ia - ib;
                    ia = s;
                }
            }
        }
        return s;
    }

Answer 14

هل هو مكان آخر؟

أباتشي! - لديها كل من GCD و LCM ، رائع جدا!

ومع ذلك ، نظرًا لعمق تنفيذها ، يكون الأمر أبطأ مقارنةً بالنسخة المكتوبة باليد البسيطة (إذا كان ذلك مهمًا).

Answer 15

وظائف GCD تلك التي توفرها المشاعات و الجوافة لديك بعض الاختلافات.

• المشاعات ما هي رمي ArithematicException.class فقط ل Integer.MIN_VALUE أو Long.MIN_VALUE.
  • خلاف ذلك ، يتعامل مع القيمة كقيمة مطلقة.
• الجوافة ترمي IllegalArgumentException.class لأي قيم سلبية.

Answer 16

النسبة المئوية لمنحنا GCD بين رقمين ، فهذا يعني:- ٪ أو mod of big_number/small_number هي = gcd ، ونكتبها على java مثل هذا big_number % small_number.

ex1: بالنسبة إلى اثنين من الأعداد الصحيحة

  public static int gcd(int x1,int x2)
    {
        if(x1>x2)
        {
           if(x2!=0)
           {
               if(x1%x2==0)     
                   return x2;
                   return x1%x2;
                   }
           return x1;
           }
          else if(x1!=0)
          {
              if(x2%x1==0)
                  return x1;
                  return x2%x1;
                  }
        return x2;
        } 

EX2: لثلاثة أعداد صحيحة

public static int gcd(int x1,int x2,int x3)
{

    int m,t;
    if(x1>x2)
        t=x1;
    t=x2;
    if(t>x3)
        m=t;
    m=x3;
    for(int i=m;i>=1;i--)
    {
        if(x1%i==0 && x2%i==0 && x3%i==0)
        {
            return i;
        }
    }
    return 1;
}