inthink.guide
المتجرالعودة إلى الرئيسية

العب. توقّع. افهم.

برج هانوي

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

العب برج هانوي
ABCالقرص 44القرص 33القرص 22القرص 11

أبعد مجموعة الأقراص الصغيرة لتحرير القرص الأكبر.

قواعد برج هانوي

  1. انقل المجموعة كاملة من العمود A إلى العمود C.
  2. انقل قرصًا واحدًا في كل مرة، وخذ القرص العلوي فقط.
  3. لا تضع قرصًا كبيرًا فوق قرص أصغر منه.

العب برج هانوي

اختر عمود البداية ثم عمود الوجهة. الأرقام تدل على الحجم: 1 هو الأصغر. تراجع عن حركة أو ابدأ من جديد لتجربة طريقة أخرى.

عدد الحركات: 0
ABCالقرص 33القرص 22القرص 11

اختر عمود البداية ثم الوجهة.

تبدأ التلميحات من وضع لوحتك ولا تحرّك الأقراص بدلًا منك. حتى المسار الأطول المسموح يمكن إكماله.

كيف تحل برج هانوي

فكّر أولًا في القرص الأكبر. في مثال الأقراص الأربعة، تحجبه ثلاثة أقراص أصغر. حل هذه المسألة الصغيرة قبل تحريك القرص 4.

  1. أبعد المجموعة الصغيرة

    انقل الأقراص 1 و2 و3 من A إلى B مستخدمًا C عمودًا مساعدًا. اترك القرص 4 على A. يصبح C فارغًا ويظهر القرص 4.

    ABCالقرص 44القرص 33القرص 22القرص 11

  2. انقل القرص الأكبر

    انقل القرص 4 من A إلى C. بهذه الحركة يصل القرص الأكبر إلى مكانه النهائي.

    ABCالقرص 44القرص 33القرص 22القرص 11

  3. أعد المجموعة الصغيرة إلى الوجهة

    انقل الأقراص 1 و2 و3 من B إلى C مستخدمًا A مساعدًا. توضع فوق القرص 4 ويكتمل اللغز.

    ABCالقرص 44القرص 33القرص 22القرص 11

تستخدم كل مجموعة أصغر الخطة نفسها: أبعد ما فوق أكبر أقراصها، وانقل ذلك القرص، ثم أعد المجموعة الصغيرة فوقه. عند بقاء قرص واحد انقله مباشرة. هذا هو الاستدعاء الذاتي؛ تتغير أدوار البداية والوجهة والمساعد مع كل مسألة فرعية.

تعلّم بتوقّع الهدف التالي

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

1. افسح الطريق للقرص الأكبر

شاهد ثلاثة أقراص صغيرة تفسح المجال للقرص 4. توقّع أين يجب أن تكون قبل تحريك الأكبر.

مثال مستقل بأربعة أقراص

الهدف: نقل 3 أقراص من A إلى B باستخدام C مساعدًا.

ABCالقرص 44القرص 33القرص 22القرص 11

افسح الطريق أولًا: انقل الأقراص الثلاثة العليا من A إلى B.

الخطوة 0 من 8

2. كرّر المسألة الأصغر

القرص 4 موجود على C. تبقى المسألة نفسها بثلاثة أقراص وأدوار مختلفة للأعمدة.

مثال مستقل بأربعة أقراص

الهدف: نقل 3 أقراص من B إلى C باستخدام A مساعدًا.

ABCالقرص 44القرص 33القرص 22القرص 11

اترك القرص 4 على C. حل الآن مسألة الأقراص الثلاثة من B إلى C.

لنقل ثلاثة أقراص من B إلى C باستخدام A، أين يذهب القرص 1 أولًا؟

الخطوة 0 من 7

الحلول خطوة بخطوة

تبدأ الأمثلة بكل الأقراص على A وتنتهي على C. افتح أي مثال مباشرة دون تغيير لعبتك.

أقل عدد من الحركات

T(n) = 2T(n − 1) + 1 = 2ⁿ − 1

ينقل الحل القياسي المجموعة الصغيرة مرتين والقرص الأكبر مرة: T(n) = 2T(n − 1) + 1. يحتاج قرص واحد حركة واحدة، لذا فالحد الأدنى لعدد n من الأقراص هو 2ⁿ − 1.

3 أقراص: 7 حركات. 4 أقراص: 15 حركة. 5 أقراص: 31 حركة.

3 أقراص — 7 حركات

البداية: كل الأقراص على A. الوجهة: C. القرص 1 هو الأصغر.

  1. انقل القرص 1 من A إلى C.
  2. انقل القرص 2 من A إلى B.
  3. انقل القرص 1 من C إلى B.
  4. انقل القرص 3 من A إلى C.
  5. انقل القرص 1 من B إلى A.
  6. انقل القرص 2 من B إلى C.
  7. انقل القرص 1 من A إلى C.
4 أقراص — 15 حركات

البداية: كل الأقراص على A. الوجهة: C. القرص 1 هو الأصغر.

  1. انقل القرص 1 من A إلى B.
  2. انقل القرص 2 من A إلى C.
  3. انقل القرص 1 من B إلى C.
  4. انقل القرص 3 من A إلى B.
  5. انقل القرص 1 من C إلى A.
  6. انقل القرص 2 من C إلى B.
  7. انقل القرص 1 من A إلى B.
  8. انقل القرص 4 من A إلى C.
  9. انقل القرص 1 من B إلى C.
  10. انقل القرص 2 من B إلى A.
  11. انقل القرص 1 من C إلى A.
  12. انقل القرص 3 من B إلى C.
  13. انقل القرص 1 من A إلى B.
  14. انقل القرص 2 من A إلى C.
  15. انقل القرص 1 من B إلى C.
5 أقراص — 31 حركات

البداية: كل الأقراص على A. الوجهة: C. القرص 1 هو الأصغر.

  1. انقل القرص 1 من A إلى C.
  2. انقل القرص 2 من A إلى B.
  3. انقل القرص 1 من C إلى B.
  4. انقل القرص 3 من A إلى C.
  5. انقل القرص 1 من B إلى A.
  6. انقل القرص 2 من B إلى C.
  7. انقل القرص 1 من A إلى C.
  8. انقل القرص 4 من A إلى B.
  9. انقل القرص 1 من C إلى B.
  10. انقل القرص 2 من C إلى A.
  11. انقل القرص 1 من B إلى A.
  12. انقل القرص 3 من C إلى B.
  13. انقل القرص 1 من A إلى C.
  14. انقل القرص 2 من A إلى B.
  15. انقل القرص 1 من C إلى B.
  16. انقل القرص 5 من A إلى C.
  17. انقل القرص 1 من B إلى A.
  18. انقل القرص 2 من B إلى C.
  19. انقل القرص 1 من A إلى C.
  20. انقل القرص 3 من B إلى A.
  21. انقل القرص 1 من C إلى B.
  22. انقل القرص 2 من C إلى A.
  23. انقل القرص 1 من B إلى A.
  24. انقل القرص 4 من B إلى C.
  25. انقل القرص 1 من A إلى C.
  26. انقل القرص 2 من A إلى B.
  27. انقل القرص 1 من C إلى B.
  28. انقل القرص 3 من A إلى C.
  29. انقل القرص 1 من B إلى A.
  30. انقل القرص 2 من B إلى C.
  31. انقل القرص 1 من A إلى C.

ماذا لو اختلفت لوحتي عن المثال؟

يمكن لكل وضع يحترم ترتيب الأحجام الوصول إلى C. تكرار وضع سابق حلقة وليس طريقًا مسدودًا. تنطبق الصيغة على البداية القياسية، ولا تعطي الحركات المتبقية لأي وضع عشوائي. اطلب تلميحًا من وضعك الفعلي.

الألغاز →