تمارين

مراجعة المفاهيم

أي المهام تصلح للتقسيم والتغلب؟

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

ترتيب مصفوفة غير مرتبة.
إيجاد القيمة العظمى في مصفوفة.
تنفيذ سلسلة من عمليات المكدس push(x) وpop() بالترتيب، وإخراج العنصر الذي تُرجعه كل عملية pop().

الإجابة

مناسبة: قسّم المصفوفة إلى نصفين، ورتّب كل نصف باستقلالية، ثم ادمجهما في زمن $O(n)$ . هذا هو بالضبط الترتيب بالدمج.
يمكن استخدام التقسيم والتغلب، لكنه لا يقلل إجمالي العمل. فالنصفان لا يزالان يتطلبان فحص جميع العناصر $n$ إجمالاً، لذا يبقى التعقيد الزمني $O(n)$ ، تماماً مثل المسح المباشر.
لا يمكن حل النصفين باستقلالية. فمحتوى المكدس في بداية النصف الثاني يعتمد على نتيجة تنفيذ النصف الأول، لذا لا يمكن إكمال النصفين دون معرفة نتائج كل منهما.

كيف يقلل الرفع إلى قوة بالتربيع من الحسابات

تستخدم الدالة التعاودية التالية التقسيم والتغلب لحساب $x^n$ :

/* الرفع إلى قوة بالتربيع */
func fastPow(x, n int) int {
	if n == 0 {
		return 1
	}
	half := fastPow(x, n/2)
	if n%2 == 0 {
		return half * half
	}
	return half * half * x
}

TypeScript

/* الرفع إلى قوة بالتربيع */
function fastPow(x: number, n: number): number {
    if (n === 0) {
        return 1;
    }
    const half = fastPow(x, Math.floor(n / 2));
    if (n % 2 === 0) {
        return half * half;
    }
    return half * half * x;
}

اضبط x = 3 وn = 5، واستخدم هذه الدالة لحساب النتيجة:

مع تقدّم الاستدعاءات التعاودية، ما القيم التي تأخذها الوسيطة n بالترتيب؟
بدءاً من أعمق استدعاء، ما القيمة التي يعيدها كل مستوى؟
لماذا ينبغي تخزين النتيجة التعاودية في half بدلاً من استدعاء المسألة الجزئية نفسها مرة على كل جانب من جانبي الضرب؟

الإجابة

تأخذ الوسيطة القيم 5 → 2 → 1 → 0. فالأُس يُنصَّف في كل خطوة حتى الوصول إلى الحالة الأساسية.
عندما n = 0، تعيد الدالة 1. وعندما n = 1، تعيد $1×1×3=3$ . وعندما n = 2، تعيد $3×3=9$ . وعندما n = 5، تعيد $9×9×3=243$ .
إذا استُدعيت المسألة الجزئية نفسها مرة على كل جانب من جانبي الضرب، فسيؤدي الاستدعاءان التعاوديان الحساب نفسه بالضبط. أما تخزين النتيجة في half فيعني أن كل مستوى يقوم باستدعاء تعاودي واحد فقط، لذا يكون عمق التعاود نحو $\log n$ . أما إجراء استدعاءين فسيسبب قدراً كبيراً من الحساب المتكرر.

تقسيم متتاليات الاجتياز إلى شجرة فرعية يسرى ويمنى

تحتوي شجرة ثنائية على عقد غير مكررة. واجتيازاها بالطلب المسبق وبالطلب الداخلي هما:

الطلب المسبق: [A, B, D, E, C]
الطلب الداخلي: [D, B, E, A, C]

قسّم المتتاليتين مرة واحدة فقط عند الجذر. لا تحتاج إلى المتابعة تعاودياً أو رسم الشجرة كاملة:

ما العقدة الجذر؟
أي المتتاليات الجزئية من الاجتياز بالطلب الداخلي تقابل الشجرة الفرعية اليسرى واليمنى؟
أي المتتاليات الجزئية من الاجتياز بالطلب المسبق تقابل الشجرة الفرعية اليسرى واليمنى؟ وما العقد التي تعد أبناءً مباشرين للجذر؟

الإجابة

أول عقدة في الاجتياز بالطلب المسبق هي الجذر، لذا الجذر هو A.
يقسم A الاجتياز بالطلب الداخلي إلى جزأين: [D, B, E] للشجرة الفرعية اليسرى و[C] للشجرة الفرعية اليمنى.
تحتوي الشجرة الفرعية اليسرى على 3 عقد، لذا تنتمي العناصر الثلاثة التالية للجذر A في الطلب المسبق إلى الشجرة الفرعية اليسرى، وهي [B, D, E]. أما [C] المتبقية فتنتمي إلى الشجرة الفرعية اليمنى. لذلك، الابن الأيسر للجذر هو B، والابن الأيمن هو C.

تمارين برمجية

الرفع إلى قوة بالتربيع

بالنظر إلى عدد حقيقي x وعدد صحيح n، احسب $x^n$ دون استدعاء دالة الرفع إلى قوة المدمجة في اللغة. استخدم التقسيم والتغلب التعاودي: نصّف الأُس في كل خطوة وأعد استخدام نتيجة المسألة الجزئية المحسوبة سابقاً. يعرّف هذا التمرين $x^0=1$ ، بما في ذلك عندما x = 0. وعندما n < 0 يكون x != 0 مضموناً، ويمكن تحويل الإجابة إلى $(1/x)^{-n}$ .

تلميحات

عندما يكون n مساوياً 0، تكون الإجابة 1
بعد حساب x مرفوعاً إلى القوة n // 2، خزّن النتيجة في half بدلاً من إجراء الاستدعاء التعاودي مرة ثانية
عندما n < 0، غيّر x أولاً إلى 1 / x ثم غيّر n إلى -n؛ في C++ أو Java، حوّل n أولاً إلى عدد صحيح 64 بت لتجنب الفائض عند نفي أصغر عدد صحيح 32 بت

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

السابق ملخص التالي التتبّع الرجعي