Competitive Programming Academy · درس

البحث الثنائي عن الإجابة

تخمين النتيجة والتحقق من إمكانية تحقيقها

البحث الثنائي عن الإجابة درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.

خمّن ثم تحقّق

أحيانًا لا يمكنك حساب الإجابة مباشرةً، لكن يمكنك التحقق من تخمين. ويحوّل البحث الثنائي عن الإجابة مسائل التحسين الصعبة إلى عملية تحقق سهلة.

# guess X, ask: is X feasible?

الخاصية السحرية

ينجح ذلك عندما تكون قابلية التنفيذ رتيبة: فإذا نجحت قيمة، فإن كل قيمة أكبر منها أو أصغر، بحسب المسألة، تنجح أيضًا. وهذا الترتيب هو ما تبحث عنه.

# feasible(X) true => feasible(X+1) true

حدّد نطاق الإجابة

حدّد أصغر وأكبر إجابة ممكنتين بوصفهما low وhigh. ففي مسألة الحد الأدنى للسعة، تكون low عنصرًا واحدًا وhigh هو المجموع الكلي.

low, high = max(weights), sum(weights)

اكتب اختبار قابلية التنفيذ

جوهر الطريقة هو دالة can(X) التي تعيد true إذا كان التخمين X قابلًا للتحقيق. وعادةً ما تعمل في زمن خطي.

def can(cap):
    # simulate and return True/False
    ...

مثال: الشحن خلال D يومًا

مع إعطاء السعة اليومية cap، املأ الأيام بطريقة جشعة واحسب عددها. تكون can(cap) صحيحة عندما يبقى عدد الأيام ضمن الحد D.

def can(cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days += 1; load = 0
        load += w
    return days <= D

ابحث عن الحد الأدنى للسعة

تريد أصغر cap ينجح. هذا بحث عن أول true ضمن السعات، لذا أعد استخدام قالب high = mid.

while low < high:
    mid = (low + high) // 2

احتفظ بالنصف القابل للتنفيذ

إذا كانت can(mid) صحيحة، فقد تظل سعة أصغر صالحة، لذا عيّن high = mid. وإلا فارفع الحد الأدنى باستخدام low = mid + 1.

if can(mid):
    high = mid
else:
    low = mid + 1

راعِ ميزانية الوقت

التكلفة الكلية هي O(check x log range). ولا يستغرق الاختبار الخطي ضمن نطاق عرضه مليارًا تقريبًا سوى 30 اختبارًا، وهو سريع بما يكفي للحدود الصارمة.

# log2(1e9) is about 30 iterations

عظّم بدلًا من أن تصغّر

للعثور على أكبر قيمة قابلة للتنفيذ، اعكس المنطق: ابحث عن آخر true. ارفع low عندما تكون القيمة قابلة للتنفيذ، وقلّص high عندما لا تكون كذلك.

if can(mid):
    low = mid
else:
    high = mid - 1

إجابات حقيقية القيمة

بالنسبة إلى الإجابات ذات الفاصلة العائمة، كرّر عددًا ثابتًا من المرات، مثل 100 مرة، بدلًا من استخدام mid الصحيح. ففي كل جولة ينخفض طول الفاصل إلى النصف، وتصل إلى دقة شديدة الصغر بسرعة.

for _ in range(100):
    mid = (low + high) / 2

اكتشف النمط

عبارات مثل أصغر أكبر، أو أكبر أصغر، أو أصغر k ينجح، هي إشارات إلى البحث الثنائي عن الإجابة. درّب عينك على ملاحظتها.

# 'minimize the maximum' => search answer

اختبار سريع

حدّد متى ينطبق البحث الثنائي عن الإجابة.

مراجعة: ابحث عن الإجابة

يمكنك الآن تحديد نطاق الإجابة، وكتابة اختبار قابلية التنفيذ، والبحث الثنائي عن الحد الأدنى أو الأقصى. وتتحول المسائل الصعبة إلى تخمين وتحقق. 🏆

الأسئلة الشائعة

هل درس «البحث الثنائي عن الإجابة» مجاني؟

نعم — نص درس «البحث الثنائي عن الإجابة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.

ماذا ستتعلم في «البحث الثنائي عن الإجابة»؟

تخمين النتيجة والتحقق من إمكانية تحقيقها تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.

هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟

لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.

كم من الوقت يستغرق درس «البحث الثنائي عن الإجابة»؟

معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.

هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟

نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.

جميع الدروس في هذه الدورة

← العودة إلى Competitive Programming Academy