الإقليدية القاسم المشترك الأعظم لأكثر من رقمين

Question

ويمكن للشخص أن تعطي المثال للعثور على خوارزمية القاسم الأعظم المشترك لأكثر من رقمين؟

وأعتقد أن لغة البرمجة لا يهم.

Answer 1

وتبدأ مع الزوج الأول والحصول على GCD الخاصة بهم، ثم أخذ GCD ذلك نتيجة وعدد المقبل. التحسين الواضح هو أنك يمكن أن تتوقف إذا تصل إلى GCD تشغيل أي وقت مضى 1. أنا أشاهد هذا واحد لمعرفة ما إذا كان هناك أي تحسينات أخرى. :)

وأوه، وهذا يمكن أن يكون بشكل متوازي بسهولة منذ العمليات تبادلي / النقابي.

Answer 2

ووGCD من 3 أرقام يمكن حسابها كما gcd(a, b, c) = gcd(gcd(a, b), c). يمكنك تطبيق الخوارزمية الإقليدية، والإقليدية الموسعة أو الخوارزمية GCD الثنائية تكرارا والحصول على الإجابة. أنا لست على علم بأي (أكثر ذكاء؟) طرق أخرى لإيجاد GCD، للأسف.

Answer 3

وقليلا في وقت متأخر إلى الحزب وأنا أعلم، ولكن تنفيذ جافا سكريبت بسيط، وذلك باستخدام وصف سام هارويل من الخوارزمية:

function euclideanAlgorithm(a, b) {
    if(b === 0) {
        return a;
    }
    const remainder = a % b;
    return euclideanAlgorithm(b, remainder)
}

function gcdMultipleNumbers(...args) { //ES6 used here, change as appropriate
  const gcd = args.reduce((memo, next) => {
      return euclideanAlgorithm(memo, next)}
  );

  return gcd;
}

gcdMultipleNumbers(48,16,24,96) //8

Answer 4

في جافا (ليس الأمثل):

public static int GCD(int[] a){
    int j = 0;

    boolean b=true;
    for (int i = 1; i < a.length; i++) {
        if(a[i]!=a[i-1]){
            b=false;
            break;
        }
    }
    if(b)return a[0];
    j=LeastNonZero(a);
    System.out.println(j);
    for (int i = 0; i < a.length; i++) {
        if(a[i]!=j)a[i]=a[i]-j;
    }
    System.out.println(Arrays.toString(a));
    return GCD(a);
}

public static int LeastNonZero(int[] a){
    int b = 0;
    for (int i : a) {
        if(i!=0){
            if(b==0||i<b)b=i;
        }
    }
    return b;
}

Answer 5

وأنا فقط بتحديث الصفحة المعرفة في هذا الشأن.

[ https://en.wikipedia.org/wiki/Binary_GCD_algorithm# C.2B.2B_template_class]

وهذا يأخذ عدد التعسفي من الشروط. استخدام GCD (5، 2، 30، 25، 90، 12)؛

template<typename AType> AType GCD(int nargs, ...)
{
    va_list arglist;
    va_start(arglist, nargs);

    AType *terms = new AType[nargs];

    // put values into an array
    for (int i = 0; i < nargs; i++) 
    {
        terms[i] = va_arg(arglist, AType);
        if (terms[i] < 0)
        {
            va_end(arglist);
            return (AType)0;
        }
    }
    va_end(arglist);

    int shift = 0;
    int numEven = 0;
    int numOdd = 0;
    int smallindex = -1;

    do
    {
        numEven = 0;
        numOdd = 0;
        smallindex = -1;

        // count number of even and odd
        for (int i = 0; i < nargs; i++)
        {
            if (terms[i] == 0)
                continue;

            if (terms[i] & 1)
                numOdd++;
            else
                numEven++;

            if ((smallindex < 0) || terms[i] < terms[smallindex])
            {
                smallindex = i;
            }
        }

        // check for exit
        if (numEven + numOdd == 1)
            continue;

        // If everything in S is even, divide everything in S by 2, and then multiply the final answer by 2 at the end.
        if (numOdd == 0)
        {
            shift++;
            for (int i = 0; i < nargs; i++)
            {
                if (terms[i] == 0)
                    continue;

                terms[i] >>= 1;
            }
        }

        // If some numbers in S  are even and some are odd, divide all the even numbers by 2.
        if (numEven > 0 && numOdd > 0)
        {
            for (int i = 0; i < nargs; i++)
            {
                if (terms[i] == 0)
                    continue;

                if ((terms[i] & 1)  == 0) 
                    terms[i] >>= 1;
            }
        }

        //If every number in S is odd, then choose an arbitrary element of S and call it k.
        //Replace every other element, say n, with | n−k | / 2.
        if (numEven == 0)
        {
            for (int i = 0; i < nargs; i++)
            {
                if (i == smallindex || terms[i] == 0)
                    continue;

                terms[i] = abs(terms[i] - terms[smallindex]) >> 1;
            }
        }

    } while (numEven + numOdd > 1);

    // only one remaining element multiply the final answer by 2s at the end.
    for (int i = 0; i < nargs; i++)
    {
        if (terms[i] == 0)
            continue;

        return terms[i] << shift;
    }
    return 0;
};

Answer 6

لgolang، وذلك باستخدام ما تبقى

func GetGCD(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func GetGCDFromList(numbers []int) int {
    var gdc = numbers[0]
    for i := 1; i < len(numbers); i++ {
        number := numbers[i]
        gdc  = GetGCD(gdc, number)
    }
    return gdc
}