الخوارزمية الإقليدية: شرح GCD (القاسم المشترك الأكبر) باستخدام أمثلة C ++ و Java

بالنسبة لهذا الموضوع ، يجب أن تعرف أولاً القاسم المشترك الأكبر (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 ، فلنقم بتطبيق الخوارزمية الإقليدية-

بافتراض أنك تريد حساب 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: الإنهاء

كود جافا سكريبت لأداء 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)); } 

كود C لأداء GCD باستخدام العودية

int gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a); } 

كود C ++ لأداء GCD-

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

كود Python لأداء GCD باستخدام Recursion

def gcd(a, b): if b == 0: return a: else: return gcd(b, (a % b)) 

كود جافا لأداء GCD باستخدام العودية

static int gcd(int a, int b) { if(b == 0) { return a; } 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  للأرقام بنفس الطريقة.

ما هي الخوارزمية الإقليدية الموسعة؟

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

الفأس + ب = gcd (أ ، ب)

يُعرف كل من x و y أيضًا بمعاملات هوية بيزوت.

كود ج للخوارزمية الإقليدية الموسعة

struct Triplet{ int gcd; int x; int y; }; Triplet gcdExtendedEuclid(int a,int b){ //Base Case if(b==0){ Triplet myAns; myAns.gcd = a; myAns.x = 1; myAns.y = 0; return myAns; } Triplet smallAns = gcdExtendedEuclid(b,a%b); //Extended euclid says Triplet myAns; myAns.gcd = smallAns.gcd; myAns.x = smallAns.y; myAns.y = (smallAns.x - ((a/b)*(smallAns.y))); return myAns; }