برج هانوي هي لعبة ألغاز كلاسيكية تم إنشاؤها في الصين القديمة ولا تزال واحدة من أكثر الألعاب شعبية في العالم. يتكون اللغز من ثلاثة قضبان ومجموعة من الأقراص ذات الأحجام المختلفة التي يمكن نقلها بين القضبان.
الهدف من اللعبة هو نقل جميع الأقراص من قضيب إلى آخر ، مع مراعاة قاعدتين بسيطتين: يمكنك فقط تحريك قرص واحد في كل مرة ، ولا يمكنك وضع قرص أكبر على قرص أصغر.
لحل هذا اللغز ، هناك خوارزمية خاصة تسمح لك بإكمال المهمة بأقل عدد من الحركات. تتكون الخوارزمية من عدة خطوات بسيطة يجب تكرارها حتى يتم الوصول إلى الهدف.
جوهر الخوارزمية هو نقل جميع الأقراص ، باستثناء أكبرها ، إلى القضيب الثالث. ثم انقل أكبر قرص إلى القضيب الثاني. وأخيرا ، انقل جميع الأقراص الأخرى من القضيب الثالث إلى الثاني. نتيجة لذلك ، يتم الحصول على الترتيب الصحيح للأقراص على القضيب الثاني.
- تاريخ برج هانوي
- الغرض من اللغز
- خوارزمية الحل
- مثال على حل اللغز
- سؤال وجواب
- ما هو لغز برج هانوي?
- ما هي الخوارزميات الموجودة لحل لغز برج هانوي?
تاريخ برج هانوي
برج هانوي هو واحد من الألغاز الشهيرة التي ربما تم إنشاؤها في فيتنام في القرن ال19. ويسمى أيضا" برج براهما "أو"برج هانوي".
على الرغم من أن الأصل الدقيق للغز غير معروف ، إلا أن هناك العديد من الأساطير والقصص حول هذا البرج. تقول إحدى الأساطير الأكثر شعبية أنه في العصور القديمة في فيتنام كان هناك دير يعتني فيه الرهبان بثلاثة دبابيس ، تم وضع حلقات على كل منها. كان هدف الرهبان هو تحريك الحلقات بحيث ينتهي بهم الأمر على دبوس آخر ، مع مراعاة القواعد التالية: يجب ألا تحتوي كل منصة على حلقة أكبر على حلقة أصغر ، ويمكن تحريك حلقة واحدة فقط في كل مرة.
انتشرت شهرة برج هانوي في القرن 19 بفضل عالم الرياضيات الفرنسي إدوارد لوكا ، الذي أدرجه في كتابه "الهندسة التعليمية". بعد ذلك ، تم التعرف على اللغز في جميع أنحاء العالم ، وأصبح شائعا بين عشاق الألغاز وعلماء الرياضيات.
يحتوي برج هانوي على العديد من الاختلافات ، بما في ذلك عدد أكبر من المسامير والخواتم ، مما يزيد من صعوبة اللغز. إنه يلتقط الخيال ويثير الاهتمام ببساطته في الشكل ، ولكن تعقيد الحل.
الغرض من اللغز
الهدف من لغز برج هانوي هو نقل جميع الأقراص من قضيب أ إلى قضيب ج باستخدام قضيب ب ، مع مراعاة قواعد معينة:
- يمكن نقل قرص واحد فقط في كل خطوة.
- لا يمكن إجراء الحركة إلا عن طريق تحريك القرص العلوي من قضيب إلى آخر.
- لا يمكن وضع قرص أكبر على قرص أصغر ، أي أنه يجب دائما استيفاء الشرط: يكون نصف قطر القرص العلوي على قضيب النهاية دائما أقل من نصف قطر القرص على قضيب البداية.
الهدف من اللغز هو العثور على الخوارزمية المثلى لنقل جميع الأقراص أولا من قضيب أ إلى قضيب ب ، ثم من قضيب ب إلى قضيب ج.
خوارزمية الحل
برج هانوي عبارة عن لغز يتكون من ثلاثة قضبان وعدة أقراص بأحجام مختلفة يمكن وضعها على القضبان. الهدف من اللعبة هو نقل جميع الأقراص من قضيب إلى آخر ، مع الحفاظ على الترتيب الأصلي.
يمكن استخدام خوارزمية متكررة لحل برج هانوي:
- تحقق مما إذا كان عدد الأقراص هو 1 ، انقله من قضيب المصدر إلى قضيب النهاية.
- خلاف ذلك:
في كل مرة تقوم فيها بتحريك القرص ، يجب أن تأخذ في الاعتبار أحجامها بحيث يكون القرص الأصغر دائما في الأعلى. يجب أيضا أخذ ترتيب القضبان في الاعتبار: الأولي والمساعد والنهائي. سيتم تكرار الخوارزمية بشكل متكرر حتى يتم نقل جميع الأقراص إلى القضيب النهائي.
تقريبا ، يمكن تمثيل الخوارزمية على النحو التالي:
- حرك القرص 1 من قضيب البداية إلى قضيب النهاية.
- نقل القرص 2 من قضيب المصدر إلى قضيب مساعد.
- نقل القرص 1 من قضيب نهاية إلى قضيب مساعد.
- حرك القرص 3 من قضيب البداية إلى قضيب النهاية.
- نقل القرص 1 من قضيب مساعد إلى قضيب المصدر.
- نقل القرص 2 من قضيب مساعد لقضيب نهاية.
- حرك القرص 1 من قضيب البداية إلى قضيب النهاية.
باستخدام خوارزمية العودية يسمح لك لحل برج هانوي مع أي عدد من الأقراص ، على الرغم من أن وقت التنفيذ سوف تزيد مع زيادة عدد الأقراص.
مثال على حل اللغز
لنفكر في مثال لحل لغز برج هانوي بثلاثة أقراص:
- لنبدأ من وضع البداية ، حيث توجد جميع الأقراص على القضيب الأول ، مرتبة حسب الحجم من الأكبر إلى الأصغر.
- لحل المشكلة ، سنحتاج إلى تكرار الخطوات التالية مرتين:
- الخطوة 1: حرك القرص من المستوى العلوي للقضيب الأول إلى المستوى العلوي للقضيب الثاني.
- الخطوة 2: تحريك القرص من المستوى العلوي للقضيب الأول إلى المستوى العلوي للقضيب الثالث.
- الخطوة 3: حرك القرص من المستوى العلوي للقضيب الثاني إلى المستوى العلوي للقضيب الثالث.
- نتيجة لذلك ، بعد تكرارين ، ستنتقل جميع الأقراص من القضيب الأول إلى القضيب الثالث ، حيث سيتم ترتيبها بالترتيب الصحيح.
وبالتالي ، فإن الخوارزمية التقريبية لحل لغز برج هانوي تتكون من تكرار ثلاث خطوات رئيسية في تسلسل معين حتى يتم تحقيق النتيجة النهائية.
سؤال وجواب
ما هو لغز برج هانوي?
لغز برج هانوي هو لغز منطقي يتكون من ثلاثة قضبان وعدة أقراص بأقطار مختلفة ، والتي يتم تعليقها على أحد القضبان بترتيب تصاعدي للأقطار من أعلى إلى أسفل. الهدف من اللعبة هو نقل جميع الأقراص من قضيب إلى آخر ، مع استخدام القضيب الثالث كوسيط.
ما هي الخوارزميات الموجودة لحل لغز برج هانوي?
هناك العديد من الخوارزميات لحل لغز برج هانوي ، بما في ذلك خوارزمية متكررة تتعلق بنظرية الأعداد والبرمجة الديناميكية. الخوارزمية العودية هي طريقة حل كلاسيكية. يعتمد على مبدأ فرق تسد ، ويتكون من أقراص متحركة بشكل متكرر من قضيب إلى آخر. تعتمد البرمجة الديناميكية على فكرة حفظ النتائج الوسيطة ، والتي تتجنب الحسابات المتكررة وتسرع عملية حل الألغاز.