لما كنا صغيرين مش فاكر ابتدائى ولا اعدادى كانو بيدونا حاجة اسمها العامل المشترك الاكبر الى هو دلوقتى اسمه
دلوقتى لو قلنا عايزين العامل المشترك الاكبر (GCD) لرقمين يعنى المطلوب منى أدور على أكبر رقم هما الاتنين بيقبلوا القسمة عليه
ناخد مثال 6 و 16
هايطلع ان أكبر رقم الرقيمن يقبلو القسمه عليه هو 2 عشان ال 16 تقبل القسمه على ال 2 وال 6 تقبل القسمه على 2 ومفيش اى رقم تانى أكبر من ال 2 ال 16 و 6 بيقبلوا القسمة عليه معا .
دلوقتى احنا لو هنجيب العامل المشترك الاكبر لرقمين بدون Algorithm هنعمل ايه ؟؟؟
ايوة صح انت(ى) بتفكر(ى) صح
· هناخد الرقم الاصغر فيهم.
· نشوف هل بيقبل القسمة على الرقم الاكبر ولا لأ.
· لو بيقبل القسمة يبقى قشطة هو ده ال العامل المشترك الاكبر (GCD) .
· ولو مش بيقبل يبقى انقص واحد واجرب هل بيقبل القسمة على الرقمين ولا لأ لحد اما الاقى رقم بيبقى القسمة على الرقمين ويبقى هو ده العامل المشترك الاكبر (GCD).
طبعا الكلام ده سليم ولكن هياخد وقت كبير جدا جدا مع الارقام الكبيرة .... علشان كده "اقليدس" فكر وطلعلنا ب Algorithm وسماه "Euclid's algorithm"
ال Algorithm بيقول الاتى
"العامل المشترك الأكبر لعددين طبيعيين A ، B يساوي العامل المشترك الأكبر للعدد الثاني B و باقي قسمة A على B ، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر ، عندئذ يكون القاسم المشترك الأكبر هو العدد الآخر." ..... المصدر ويكيبديا
ناخد مثال علشان الموضوع يبقى أوضح
العامل المشترك الأكبر(GCD) للعددين 252 و 198 :
252 = 198 * 1 + 54
دلوقتى 54 هو باقي قسمة 252 على 198
نقوم نروح نجيب العامل المشترك الاكبر (GCD) للعددين 198 و 54
198 = 54 * 3 + 36
36 هو باقي القسمة.
نكرر العملية المرة دى مع : 54 و 36
54 = 36 * 1 + 18
ومرة ثالثة
36 = 18 * 2 + 0
هنا وصلنا للصفر فيكون العدد الثاني 18 هو العامل المشترك الأكبر.
طبعا احنا هنا فى 3 معادلات جبنا العامل المشترك الاكبر انما لو كنا مشينا زى ما قلنا فى الاول كنا هناخد وقت كبير جدا لاننا كنا هنمشى من 198 لحد 18 ونعمل عمليات طول الطريق
ودى مسألة علشان لو عايزين تحلوا على ال GCD
"Euclid's algorithm" ده
a = a % b;
a ^= b;
b ^= a;
a ^= b;
}
ولو فى أى اسألة اتفضلوا اسألوا
ودى نسخة PDF للمقال
(GCD) Greatest common divisor
ناخد مثال 6 و 16
هايطلع ان أكبر رقم الرقيمن يقبلو القسمه عليه هو 2 عشان ال 16 تقبل القسمه على ال 2 وال 6 تقبل القسمه على 2 ومفيش اى رقم تانى أكبر من ال 2 ال 16 و 6 بيقبلوا القسمة عليه معا .
دلوقتى احنا لو هنجيب العامل المشترك الاكبر لرقمين بدون Algorithm هنعمل ايه ؟؟؟
ايوة صح انت(ى) بتفكر(ى) صح
· هناخد الرقم الاصغر فيهم.
· نشوف هل بيقبل القسمة على الرقم الاكبر ولا لأ.
· لو بيقبل القسمة يبقى قشطة هو ده ال العامل المشترك الاكبر (GCD) .
· ولو مش بيقبل يبقى انقص واحد واجرب هل بيقبل القسمة على الرقمين ولا لأ لحد اما الاقى رقم بيبقى القسمة على الرقمين ويبقى هو ده العامل المشترك الاكبر (GCD).
طبعا الكلام ده سليم ولكن هياخد وقت كبير جدا جدا مع الارقام الكبيرة .... علشان كده "اقليدس" فكر وطلعلنا ب Algorithm وسماه "Euclid's algorithm"
ال Algorithm بيقول الاتى
"العامل المشترك الأكبر لعددين طبيعيين A ، B يساوي العامل المشترك الأكبر للعدد الثاني B و باقي قسمة A على B ، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر ، عندئذ يكون القاسم المشترك الأكبر هو العدد الآخر." ..... المصدر ويكيبديا
ناخد مثال علشان الموضوع يبقى أوضح
العامل المشترك الأكبر(GCD) للعددين 252 و 198 :
252 = 198 * 1 + 54
دلوقتى 54 هو باقي قسمة 252 على 198
نقوم نروح نجيب العامل المشترك الاكبر (GCD) للعددين 198 و 54
198 = 54 * 3 + 36
36 هو باقي القسمة.
نكرر العملية المرة دى مع : 54 و 36
54 = 36 * 1 + 18
ومرة ثالثة
36 = 18 * 2 + 0
هنا وصلنا للصفر فيكون العدد الثاني 18 هو العامل المشترك الأكبر.
طبعا احنا هنا فى 3 معادلات جبنا العامل المشترك الاكبر انما لو كنا مشينا زى ما قلنا فى الاول كنا هناخد وقت كبير جدا لاننا كنا هنمشى من 198 لحد 18 ونعمل عمليات طول الطريق
ودى مسألة علشان لو عايزين تحلوا على ال GCD
"Euclid's algorithm" ده
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
وده كود تانى لل GCD ... هو معتمد على "Euclid's algorithm" لكن معمول بطريقة ثانية.
int GCD(int a,int b)
{
while (b > 0)
{
{
a = a % b;
a ^= b;
b ^= a;
a ^= b;
}
return a;
}
}
ودى نسخة PDF للمقال