خوارزمية برج هانوي: Python, C++ Code

⚡ ملخص ذكي

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

🗼 إعداد اللغز: ثلاثة أوتاد و n أقراص مكدسة بأحجام متناقصة على وتد المصدر، في انتظار نقلها إلى وتد الوجهة من خلال وتد مساعد.
📜 قواعد: لا يتحرك سوى قرص واحد في كل مرة، ولا يمكن أن يتحرك سوى القرص العلوي لأي وتد، ولا يمكن لقرص أكبر أن يستقر على قرص أصغر.
🔁 فكرة تكرارية: انقل n-1 قرصًا إلى وتد المساعدة، ثم انقل القرص الأكبر إلى وتد الوجهة، ثم انقل n-1 قرصًا من المساعد إلى الوجهة.
⏱️ تعقيد الوقت: يتطلب حل n قرصًا 2^n – 1 حركة، مما يعطي تعقيدًا زمنيًا أسيًا O(2^n) ينمو بسرعة كبيرة مع زيادة n.
🧠 تعقيد الفضاء: تحتوي مكدسة التكرار على ما يصل إلى n إطارًا في المرة الواحدة، لذا فإن تعقيد المساحة للحل التكراري هو O(n).
🛠️ التطبيقات: تدريس الاستدعاء الذاتي، ومخططات التناوب الاحتياطية، ونقل البيانات القائم على المكدس، وتسلسل الروبوتات، وفهم تصميم خوارزمية فرق تسد.

اقرأ المزيد

ما هو برج هانوي؟

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

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

في البداية، لدينا ثلاثة أوتاد أو قضبان. أحدها (الوتد أ في المثال) عليه جميع الأقراص مكدسة. الهدف هو نقل المجموعة بأكملها من قضيب (أ) إلى آخر (ج) مع مراعاة بعض القواعد المحددة.

إليكم الإعداد الأولي للغز:

مشكلة برج هانوي

وهذا هو الهدف النهائي:

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

إليكم القواعد الأساسية لبرج هانوي:

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

كانت الأسطورة الأصلية تدور حول تحريك 64 قرصًا. وكان بإمكان الكهنة تحريك قرص واحد في كل مرة وفقًا للقواعد. وبحسب الأسطورة، كانت هناك نبوءة تقول إن العالم سينتهي إذا تمكنوا من إتمام هذه المهمة. في قسم التعقيد الزمني، سنوضح أن إعداد برج هانوي باستخدام n قرصًا يتطلب 2^n - 1 حركة.

لذا، إذا احتاج الكهنة ثانية واحدة لتحريك قرص واحد، فإن إجمالي الوقت اللازم لحل اللغز سيكون 2^64 – 1 ثانية، أو ما يقرب من 584,942,417,356 سنة و26 يومًا و7 ساعات و15 ثانية.

خوارزمية برج هانوي

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

فيما يلي خطوات حل لغز برج هانوي:

انقل أقراص n-1 العلوية من الوتد المصدر إلى الوتد المساعد.
انقل القرص رقم n من وتد المصدر إلى وتد الوجهة.
انقل الأقراص المتبقية (عددها n-1) من وتد المساعدة إلى وتد الوجهة.

ملاحظة: إذا كان لدينا قرص واحد، فيمكننا نقله مباشرة من المصدر إلى الوجهة.

كيفية حل لغز برج هانوي

دعونا نوضح الخوارزمية لثلاثة أقراص. لنعتبر الوتد A هو المصدر، والوتد B هو المساعد، والوتد C هو الوجهة.

الخطوة 1) في البداية، يتم تكديس جميع الأقراص على الوتد A.

في هذه المرحلة: المصدر = الوتد أ، الوجهة = الوتد ج، المساعد = الوتد ب.

الآن، نحن بحاجة إلى نقل الأقراص n-1 العليا من المصدر إلى المساعد.

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

الخطوة 2) بما أننا نقوم باستدعاء متكرر من الوتد A مع اعتبار الوتد B هو الوجهة، فإننا نستخدم الوتد C كمساعد.

لاحظ أننا عدنا إلى المرحلة الأولى لنفس مسألة برج هانوي، ولكن الآن لقرصين. ننقل القرص رقم n-1 (أي قرص واحد) من المصدر إلى القرص المساعد، مما ينقل أصغر قرص من الوتد A إلى الوتد C.

في هذه المرحلة: المصدر = الوتد أ، الوجهة = الوتد ب، المساعد = الوتد ج.

الخطوة 3) وفقًا للخوارزمية، يتم الآن نقل القرص رقم n (الثاني) إلى الوجهة، الوتد B.

في هذه المرحلة: المصدر = الوتد أ، الوجهة = الوتد ب، المساعد = الوتد ج.

الخطوة 4) الآن، نقوم بنقل القرص رقم n-1 (القرص واحد) من وتد المساعدة C إلى وتد الوجهة B، باتباع المرحلة الثالثة من الخوارزمية.

في هذه المرحلة: المصدر = الوتد أ، الوجهة = الوتد ب، المساعد = الوتد ج.

الخطوة 5) بعد إكمال الاستدعاء المتكرر، نعود إلى إعداداتنا السابقة في المرحلة الأولى من الخوارزمية.

الخطوة 6) في المرحلة الثانية، نقوم بنقل القرص 3 من وتد المصدر A إلى وتد الوجهة C.

في هذه المرحلة: المصدر = الوتد أ، الوجهة = الوتد ج، المساعد = الوتد ب.

الخطوة 7) المهمة التالية هي نقل الأقراص المتبقية من القرص المساعد (الوتد B) إلى القرص الوجهة (الوتد C). سنستخدم القرص المصدر الأصلي (الوتد A) كقرص مساعد هذه المرة.

الخطوة 8) بما أنه لا يمكننا نقل قرصين في وقت واحد، فإننا نجري استدعاءً متكررًا للقرص 1. وفقًا لـ خوارزمية، الوجهة في هذه الخطوة هي الوتد أ.

في هذه المرحلة: المصدر = الوتد ب، الوجهة = الوتد أ، المساعد = الوتد ج.

الخطوة 9) اكتملت عملية الاستدعاء التكراري. الآن ننقل القرص 2 من مصدره إلى وجهته.

في هذه المرحلة: المصدر = الوتد ب، الوجهة = الوتد ج، المساعد = الوتد أ.

الخطوة 10) نختتم بنقل القرص المتبقي n-1 (القرص 1) من المساعد إلى الوجهة.

في هذه المرحلة: المصدر = الوتد أ، الوجهة = الوتد ج، المساعد = الوتد ب.

كنية Code برج هانوي

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
    IF disk == 1 THEN
        move disk from source to dest
    ELSE
        Tower_Of_Hanoi(disk - 1, source, helper, dest)
        move disk from source to dest
        Tower_Of_Hanoi(disk - 1, helper, dest, source)
    END IF
END Procedure

كود البرنامج في C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
    if (num == 1) {
        cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
        return;
    }
    tower_of_hanoi(num - 1, source, helper, dest);
    cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
    tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
    int num;
    cin >> num;
    printf("The sequence of moves :\n");
    tower_of_hanoi(num, "I", "III", "II");
    return 0;
}

الإخراج:

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

كود البرنامج في Python

def tower_of_hanoi(n, source, destination, helper):
    if n == 1:
        print("Move disk 1 from peg", source, "to peg", destination)
        return
    tower_of_hanoi(n - 1, source, helper, destination)
    print("Move disk", n, "from peg", source, "to peg", destination)
    tower_of_hanoi(n - 1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n, 'A', 'B', 'C')

الإخراج:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

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

فيما يلي تعقيد الزمان والمكان لبرج هانوي:

1) تعقيد الوقت:

بالنظر إلى الخوارزمية، نقوم باستدعاء متكرر لـ (n-1) قرصًا مرتين في كل استدعاء. كل استدعاء متكرر لـ (n-1) ينقسم إلى ((n-1)-1) استدعاء متكرر، وهكذا، حتى نصل إلى حالة القرص الواحد الأساسية.

لثلاثة أقراص:

يستدعي القرص 3 الدالة التكرارية للقرص 2 مرتين.
يستدعي القرص 2 الدالة التكرارية للقرص 1 مرتين.
يتحرك القرص 1 في وقت ثابت، مما يتيح الوقت اللازم لحل المسألة لثلاثة أقراص.

معبر عنه كتكرار:

= 2 × (الوقت اللازم لحل المعادلة لقرصين) + الوقت الثابت لتحريك القرص 3

= 2 × (2 × الوقت اللازم لحل قرص واحد + الوقت الثابت لتحريك القرص 2) + الوقت الثابت لتحريك القرص 3

= (2 × 2) × زمن ثابت لتحريك القرص 1 + 2 × زمن ثابت لتحريك القرص 2 + زمن ثابت لتحريك القرص 3

بالنسبة لعدد n من الأقراص، يصبح هذا كالتالي:

2^N-1 × زمن ثابت لتحريك القرص 1 + 2^N-2 × زمن ثابت لتحريك القرص 2 + ….

مجموع هذا المتتابع الهندسي يساوي O(2)ⁿ - 1)، وهو ما يتبسط إلى يا (2ⁿ)، تعقيد زمني أُسّي.

2) تعقيد المساحة:

تبلغ تعقيدات المساحة لخوارزمية برج هانوي O(n). تستخدم هذه الخوارزمية التكرارية مكدس الاستدعاءات، ويبلغ أقصى عمق للمكدس n، وهو عدد الأقراص. ولذلك فإن تعقيدات المساحة هي O(n).

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

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

الحد الأدنى لعدد الحركات لـ n قرص هو 2^n – 1. ثلاثة أقراص تحتاج إلى 7 حركات، وأربعة أقراص تحتاج إلى 15 حركة، وعشرة أقراص تحتاج إلى 1,023 حركة.

التعقيد الزمني هو O(2^n) لأن كل قرص إضافي يضاعف العمل. والمعادلة التكرارية T(n) = 2T(n-1) + 1 تُحل إلى 2^n – 1، وهي دالة أسية.

يبلغ تعقيد المساحة O(n) لأن مكدس استدعاءات التكرار يستوعب إطارًا واحدًا لكل قرص تتم معالجته. يصل أقصى عمق للتكرار إلى n، لذا فإن الذاكرة الإضافية المطلوبة تتناسب طرديًا مع عدد الأقراص.

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

تُعلّم الخوارزمية التكرار، وتُصمّم نماذج لخطط النسخ الاحتياطي والتدوير للتخزين، وتُوجّه تسلسل الذراع الروبوتية، وتظهر في اختبارات علم النفس العصبي التي تقيس القدرة على التخطيط.

تقوم وكلاء التعلم المعزز بحل لعبة برج هانوي من خلال اعتبار كل تكوين للأقراص حالةً، وكل حركة فعلًا. وهي معيار شائع للتخطيط وتعلم السياسات الهرمية.

نعم. GitHub Copilot و ChatGPT و Gemini توليد حلول تكرارية لبرج هانوي في Python, C++و Java. يجب على المطورين التحقق من الحالات الأساسية وترتيب الوسائط.

خوارزمية برج هانوي: Python, C++ Code

ما هو برج هانوي؟

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

خوارزمية برج هانوي

كيفية حل لغز برج هانوي

كنية Code برج هانوي

كود البرنامج في C++

كود البرنامج في Python

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

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

تلخيص هذه التدوينة بـ:

اشترك في النشرة الإخبارية