GCD وLCM والخوارزمية الإقليدية
حساب القواسم بسرعة ودقة
GCD وLCM والخوارزمية الإقليدية درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
سبب أهمية القواسم
تعتمد كثير من مسائل المسابقات على العوامل المشتركة بين عددين. والأداة الأكثر فائدة هنا هي GCD، أي القاسم المشترك الأكبر. 🔢
ماذا يعني GCD
إن GCD لعددين صحيحين هو أكبر عدد يقسم كليهما دون باقٍ. فبالنسبة إلى 12 و18، تكون قيمته 6، لأن 6 يقسم كليهما بالتساوي.
الطريقة البطيئة
يمكنك اختبار كل عدد بدءًا من القيمة الأصغر نزولًا حتى تجد عددًا يقسم العددين. تنجح هذه الطريقة، لكنها بطيئة جدًا مع المدخلات الكبيرة.
الفكرة الإقليدية
تُعد الخوارزمية الإقليدية الطريقة السريعة. وفكرتها الأساسية أن GCD للعددين a وb يساوي GCD للعدد b وباقي قسمة a على b.
العلاقة التكرارية
كرّر خطوة التبديل وحساب باقي القسمة حتى يصبح الباقي صفرًا. تكون آخر قيمة غير صفرية متبقية هي الإجابة، أي GCD نفسه.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aاكتب الشيفرة بنفسك
تحافظ حلقة قصيرة على استبدال الزوج حتى يصل b إلى الصفر. وتعمل هذه الطريقة في نحو log من الخطوات، بسرعة هائلة حتى مع الأعداد الضخمة.
def gcd(a, b):
while b:
a, b = b, a % b
return aاستخدم المكتبة القياسية
نادرًا ما تحتاج إلى كتابتها يدويًا. توفر Python الدالة math.gcd، وهي صحيحة وسريعة وتتعامل مع الوسائط الصفرية نيابةً عنك.
from math import gcd
print(gcd(12, 18))من GCD إلى LCM
إن LCM، أي المضاعف المشترك الأصغر، هو أصغر عدد يقسمه العددان دون باقٍ. ويرتبط مباشرةً بـ GCD الذي حسبته للتو.
صيغة LCM
اضرب العددين، ثم اقسم الناتج على GCD الخاص بهما. احرص دائمًا على إجراء القسمة أولًا لتجنّب تجاوز السعة عند التعامل مع نواتج ضرب كبيرة جدًا.
def lcm(a, b):
return a // gcd(a, b) * bحساب GCD لقائمة كاملة
لحساب GCD عبر عدة أعداد، طبّق العملية على كل زوج بالتتابع. تطبّق Python's reduce الدالة math.gcd من اليسار إلى اليمين على عناصر القائمة.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)تعامل مع حالة الصفر
بحسب التعريف، يساوي gcd(a, 0) قيمة a، بينما gcd(0, 0) يساوي 0. تساعد معرفة حالة الحافة هذه على منع الحلقات من التصرف بشكل غير صحيح عند وجود إدخال فارغ.
تحقق سريع
حان وقت التأكد من الخطوة الإقليدية الأساسية.
مراجعة
يمكنك الآن حساب GCD باستخدام الخوارزمية الإقليدية في عدد log من الخطوات، واشتقاق LCM منه، وتطبيق كليهما على قائمة كاملة. ✅
الأسئلة الشائعة
هل درس «GCD وLCM والخوارزمية الإقليدية» مجاني؟
نعم — نص درس «GCD وLCM والخوارزمية الإقليدية» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «GCD وLCM والخوارزمية الإقليدية»؟
حساب القواسم بسرعة ودقة تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «GCD وLCM والخوارزمية الإقليدية»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- GCD وLCM والخوارزمية الإقليدية
- اختبار الأولية حتى sqrt(n)
- غربال إراتوستينس
- التحليل إلى العوامل الأولية والقواسم