GCD وLCM والخوارزمية الإقليدية
حساب القواسم بسرعة ودقة
GCD وLCM والخوارزمية الإقليدية درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 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) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «GCD وLCM والخوارزمية الإقليدية»؟
حساب القواسم بسرعة ودقة تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «GCD وLCM والخوارزمية الإقليدية»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- GCD وLCM والخوارزمية الإقليدية
- اختبار الأولية حتى sqrt(n)
- غربال إراتوستينس
- التحليل إلى العوامل الأولية والقواسم