ما هي خورزميات اقليدس

خوارزمية إقليدس (Euclidean Algorithm) هي طريقة رياضيّة لحساب القاسم المشترك الأكبر بين عددين طبيعيين (يرمز لها بـGCD في المقررات الدراسية  الإنجليزية و PGCD في المقررات الفرنسية). مبدأها يقوم على تقسيم العدد الأكبر على العدد الأصغر بقسمة صحيحة و استخدام باقي القسمة في الخطوة التالية عن طريق قسمة العدد الذي كان قاسما على باقي القسمة، وتستمر العملية هكذا حتى يصبح الباقي صفرا. عندما يصبح الباقي صفرا، يكون القاسم في هذه العمليّة هو القاسم المشترك الأكبر.

وحتى لا يكون الكلام نظريّا، سأضع دالة مكتوبة مرّة بلغة Python و مرّة بلغة JavaScript تقوم بإيجاد القاسم المشترك الأكبر باستخدام خوارزميّة إقليدس (العامل % يحسب باقي القسمة مباشرة، لذلك ليس علينا أن نحسب حاصل القسمة في لغات البرمجة كما نفعل في الرياضيّات):

# دالة بلغة Python
def gcd(x, y):
  # تحقق من أن العددين موجبين
  if x < 0 or y < 0:
    return None
  # استخدم خوارزمية أقليدس باستخدام باقي القسمة
  while y != 0:
    # احفظ قيمة y في متغير مؤقت
    temp = y
    # اجعل y يساوي باقي قسمة x على y
    y = x % y
    # اجعل x يساوي قيمة y السابقة
    x = temp
  # ارجع قيمة x كالقاسم المشترك الأكبر
  return x

// دالة بلغة JavaScript
function gcd(x, y) {
  // تحقق من أن العددين موجبين
  if (x < 0 || y < 0) {
    return null;
  }
  // استخدم خوارزمية أقليدس باستخدام باقي القسمة
  while (y != 0) {
    // احفظ قيمة y في متغير مؤقت
    let temp = y;
    // اجعل y يساوي باقي قسمة x على y
    y = x % y;
    // اجعل x يساوي قيمة y السابقة
    x = temp;
  }
  // ارجع قيمة x كالقاسم المشترك الأكبر
  return x;
}

تمام ,  شكرااا جدا 

بتاريخ 2 ساعة قال حمزة عباد:

  while y != 0:

سوال لو سمحت يا أ.حمزه

هو ليه ام نبادل y به x بيظهر خطاء

while x != 0

بتاريخ 2 ساعة قال حمزة عباد:

    y = x % y

وكمان ال y هنا متغير غير y الموجود فيه المعادله

بتاريخ 9 دقائق مضت قال Ail Ahmed:

هو ليه ام نبادل y به x بيظهر خطاء

while x != 0

 

لأننا في كل حلقة نقوم بقسمة x على y ثم نحفظ باقي القسمة في y ونجعل x تساوي y لنبدأ حلقة جديدة وهكذا، وبناء عليه، يجب أن تستمر الحلقة التكرارية إلى أن تكون قيمة y تساوي صفرًا، لذلك الحلقة تعتمد على قيمة y وليس قيمة x

مثال: نبدأ بالقيم x=15, y-10

x = 15, y = 10 # الحلقة الأولى
x = 10, y = 5 # الحلقة الثانية وهي آخر حلقة

لاحظ أنه في الحلقة الثانية سيدخلها وقيمة x=10 أما قيمة y=5 لذلك في نهاية الحلقة ستكون قيمة Y=0 بينما قيمة x=5 وبالتالي لن يدخل حلقة ثالثة، ويخرج ثم يطبع قيمة x=5 وهو القاسم المشترك الأكبر بين 15 و 10

بتاريخ 5 دقائق مضت قال El Sayed El Tohamy:

لأننا في كل حلقة نقوم بقسمة x على y ثم نحفظ باقي القسمة في y ونجعل x تساوي y لنبدأ حلقة جديدة وهكذا، وبناء عليه، يجب أن تستمر الحلقة التكرارية إلى أن تكون قيمة y تساوي صفرًا، لذلك الحلقة تعتمد على قيمة y وليس قيمة x

مثال: نبدأ بالقيم x=15, y-10

x = 15, y = 10 # الحلقة الأولى
x = 10, y = 5 # الحلقة الثانية وهي آخر حلقة

لاحظ أنه في الحلقة الثانية سيدخلها وقيمة x=10 أما قيمة y=5 لذلك في نهاية الحلقة ستكون قيمة Y=0 بينما قيمة x=5 وبالتالي لن يدخل حلقة ثالثة، ويخرج ثم يطبع قيمة x=5 وهو القاسم المشترك الأكبر بين 15 و 10

 

شكراا جدا يا أ.خالد