Tower Of Hanoi using recursion

برج هانوي هي لعبة/مسألة رياضية ومنطقية مشهورة تُستخدم كثيرًا في علوم الحاسوب لشرح فكرة الـ Recursion (الاستدعاء الذاتي) والخوارزميات.

فكرة اللعبة

اللعبة تتكوّن من:

3 أعمدة (Pegs)

عدد من الأقراص (Disks) بأحجام مختلفة

الأقراص تكون مرتبة من الأكبر في الأسفل إلى الأصغر في الأعلى على العمود الأول.

الهدف هو نقل كل الأقراص من العمود الأول إلى العمود الثالث.

قواعد اللعبة

3 قواعد فقط:

مسموح تحريك قرص واحد فقط في كل خطوة.

يجب أخذ القرص الأعلى فقط من أي عمود.

لا يمكن وضع قرص كبير فوق قرص أصغر.

مثال بسيط (3 أقراص)

لو عندنا 3 أقراص، أقل عدد خطوات لحل اللعبة هو 7 خطوات.

الخطوات تقريبًا تكون كده:

نقل القرص الصغير من العمود 1 → العمود 3

نقل القرص المتوسط من العمود 1 → العمود 2

نقل القرص الصغير من العمود 3 → العمود 2

نقل القرص الكبير من العمود 1 → العمود 3

نقل القرص الصغير من العمود 2 → العمود 1

نقل القرص المتوسط من العمود 2 → العمود 3

نقل القرص الصغير من العمود 1 → العمود 3

وبكده كل الأقراص وصلت للعمود الثالث.

مثال:

عدد الأقراص أقل عدد خطوات

1 1

2 3

3 7

4 15

5 31

علاقتها بالبرمجة

المسألة دي مشهورة لأنها مثال قوي على:

Recursion

Algorithm design

Problem decomposition