كيفية استخدام الخوارزمية الإقليدية للعثور على القاسم المشترك الأكبر (GCD)

بالنسبة لهذا الموضوع ، يجب أن تعرف أولاً القاسم المشترك الأكبر (GCD) وعملية MOD.

أكبر قاسم مشترك (GCD)

يعتبر GCD المكون من عددين صحيحين أو أكثر هو أكبر عدد صحيح يقسم كل من الأعداد الصحيحة بحيث يكون الباقي صفراً.

هذا مثال:

GCD 20 ، 30 = 10 (10 هو أكبر عدد يقسم 20 و 30 مع باقي 0)

GCD لـ 42 ، 120 ، 285 = 3 (3 هو أكبر عدد يقسم 42 ، 120 و 285 مع باقي 0)

عملية "mod"

تمنحك عملية التعديل الباقي عند تقسيم عددين موجبين. نكتبها على النحو التالي:

A mod B = R

هذا يعني أن قسمة A على B تعطيك الباقي R. وهذا يختلف عن عملية القسمة التي تمنحك حاصل القسمة.

هذا مثال:

7 mod 2 = 1 (قسمة 7 على 2 تعطي الباقي 1)

42 mod 7 = 0 (قسمة 42 على 7 تعطي الباقي 0)

إذا فهمت المفهومين المذكورين أعلاه ، فستفهم بسهولة الخوارزمية الإقليدية.

الخوارزمية الإقليدية للقواسم المشتركة الأكبر (GCD)

تجد الخوارزمية الإقليدية GCD لرقمين.

ستفهم هذه الخوارزمية بشكل أفضل من خلال رؤيتها أثناء العمل. بافتراض أنك تريد حساب GCD لـ 1220 و 516 ، فلنطبق الخوارزمية الإقليدية.

الكود الزائف للخوارزمية:

الخطوة 1: لنكن a, bالرقمين

الخطوة 2: a mod b = R

الخطوة 3: اسمحوا a = bوb = R

الخطوة 4: كرر الخطوتين 2 و 3 حتى a mod bيصبح أكبر من 0

الخطوة 5: GCD = ب

الخطوة 6: الإنهاء

إليك كود Javascript لأداء GCD:

function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; }

إليك كود Javascript لأداء GCD باستخدام Recursion:

function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); }

يمكنك أيضًا استخدام الخوارزمية الإقليدية للعثور على GCD لأكثر من رقمين. نظرًا لأن GCD ارتباطية ، فإن العملية التالية صالحة:  GCD(a,b,c) == GCD(GCD(a,b), c)

احسب GCD لأول عددين ، ثم ابحث عن GCD للنتيجة والرقم التالي. مثال:GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

يمكنك العثور على GCD nللأرقام بنفس الطريقة.