تمارين
مراجعة المفاهيم
هل ستفوّت خوارزمية التباديل هذه بعض النتائج؟
تحاول خوارزمية تتبّع رجعي توليد جميع التباديل باستخدام 1, 2, 3 بهذا الترتيب. وفي كل مرة تختار عدداً x، فإنها:
- تُلحق
xبالمسار الحالي. - تُعلّم
xبأنه «مستخدم». - تملأ الموضع التالي تعاودياً.
وعندما يعود الاستدعاء التعاودي، لا يحذف الطالب سوى x من نهاية المسار ثم يجرّب العدد التالي.
- أي تبديل تولّده الخوارزمية أولاً؟ وهل تستطيع مع ذلك توليد التباديل الستة جميعها؟
- قبل العودة إلى المستوى السابق، هل يكفي حذف العدد الأخير من المسار فقط؟ وإن لم يكفِ، فما الذي يجب فعله أيضاً؟ اشرح السبب.
الإجابة
-
تولّد أولاً
[1, 2, 3]، لكنها لا تستطيع توليد جميع التباديل. فرغم أن المسار يقصر عند عودة الاستدعاءات، تظل علامات 1 و2 و3 كلها «مستخدمة»، فلا يبقى أي عدد متاح للفروع اللاحقة. -
لا يكفي. فبعد حذف
xمن نهاية المسار، يجب أيضاً إعادة تعليمxبأنه «غير مستخدم». يمثّل المسار الحالي وعلامات الاستخدام معاً حالة البحث. والاختيار يغيّر كليهما، لذا يجب أن يعيد التتبّع الرجعي كليهما قبل أن يتمكن فرع آخر من اختيارxمجدداً.
هل يهم ترتيب اختيار الأعداد؟
معطى المصفوفة المرتبة [2, 3, 5] وقيمة هدف 5. ويجوز اختيار كل عدد مراراً.
وتشترط الخوارزمية أن تظهر الأعداد على طول كل مسار بحث بترتيب غير متناقص فقط.
- ما التوليفات المتمايزة التي يمكن العثور عليها؟
- لماذا لا حاجة إلى البحث عن المجموعة نفسها من الأعداد بترتيبات مختلفة؟ وما الذي يحققه قيد الترتيب غير المتناقص؟
- افترض أن المسار الحالي
[3]والمبلغ المتبقي 2 والمرشح التالي 3. لماذا يمكن للخوارزمية أن تتوقف عن فحص جميع المرشحين اللاحقين في هذا المستوى؟
الإجابة
-
التوليفات المتمايزة هي
[2, 3]و[5]. -
يعامل هذا التمرين
[2, 3]و[3, 2]على أنهما التوليفة نفسها؛ فترتيب اختيار الأعداد لا ينشئ إجابة مختلفة. واشتراط ظهور الأعداد في المسار بترتيب غير متناقص يتيح للبحث تجاوز ترتيبات مكررة مثل[3, 2]. -
المبلغ المتبقي 2، والمرشح 3 أكبر منه أصلاً. ولأن المصفوفة مرتبة، فجميع المرشحين اللاحقين أكبر منه ولا يمكن إضافتهم إلى التوليفة الحالية، لذا يمكن للخوارزمية التوقف عن فحص هذا المستوى فوراً.
أين يمكن وضع الملكة التالية؟
ضَع الملكات صفاً صفاً على رقعة شطرنج 4 × 4، بحيث يبدأ فهرسا الصف والعمود من 0.
وقد وُضعت ملكتان عند (0, 1) و(1, 3). ويجب وضع الملكة التالية في الصف 2.
- ما الأعمدة المستبعدة لأنها تحتوي بالفعل على ملكة؟
- ومن بين الأعمدة المتبقية، ما المواضع المستبعدة لأنها تتشارك قطراً مع ملكة موجودة؟
- ما المواضع التي تبقى متاحة للتجربة في الصف 2؟
الإجابة
-
العمودان 1 و3 يحتويان بالفعل على ملكتين، لذا يُستبعد الموضعان
(2, 1)و(2, 3). -
من بين المواضع المتبقية، يقع
(2, 2)على القطر نفسه الذي يقع عليه(1, 3)، لذا يُستبعد أيضاً. أما الموضع(2, 0)فلا يتشارك عموداً ولا قطراً مع أي من الملكتين الموجودتين. -
الموضع الوحيد الذي يمكن تجربته في الصف 2 هو
(2, 0).توضح هذه الخطوة فقط أن الوضع الحالي صالح. وإذا تعذّر إكمال الرقعة لاحقاً، فيجب على الخوارزمية مع ذلك أن تتراجع وتجرّب بديلاً سابقاً.
تمارين برمجية
تباديل عناصر متمايزة
تحتوي مصفوفة الأعداد الصحيحة nums على عنصر واحد على الأقل، وجميع عناصرها متمايزة.
اذكر كل ترتيب ممكن يتكوّن باستخدام كل عنصر مرة واحدة بالضبط، وأعد كل ترتيب على هيئة مصفوفة.
ويمكن أن تظهر التباديل بأي ترتيب في النتيجة.
استخدم التتبّع الرجعي مع مصفوفة منطقية تسجّل ما إذا كان العنصر في كل موضع قد اختير بالفعل في التبديل الحالي.
تلميحات
- يشير عمق التعاود إلى موضع التبديل الذي يُملأ حالياً
- في كل مستوى، جرّب العناصر غير المستخدمة بعد فقط
- عندما يساوي طول المسار طول
nums، أضف نسخة من المسار إلى الإجابة
LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }