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

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

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

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

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

هنا هو الإعداد الأولي للغز-

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

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

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

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

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

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

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

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

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

انقل أقراص n-1 العلوية من الوتد المصدر إلى الوتد المساعد.
بعد ذلك، انقل القرص n من الوتد المصدر إلى الوتد الوجهة.
أخيرًا، انقل بقية أقراص n-1 من الوتد المساعد إلى الوتد الوجهة.

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

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

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

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

في هذه المرحلة:

المصدر = الوتد أ
الوجهة = الوتد C
المساعد = الوتد ب

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

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

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

لاحظ أننا في المرحلة الأولى مرة أخرى لنفس برج هانوي لمشكلة القرصين.

نحتاج الآن إلى نقل n-1 أو قرص واحد من المصدر إلى المساعد، ونقل أصغر قرص من الوتد A إلى الوتد C.

في هذه المرحلة:

المصدر = الوتد أ
الوجهة = الربط ب
المساعد = الوتد C

الخطوة 3) بعد ذلك، وفقًا للخوارزمية الخاصة بنا، يجب نقل احتياجات القرص n أو الثاني إلى الوجهة أو الربط B.

في هذه المرحلة:

المصدر = الوتد أ
الوجهة = الربط ب
المساعد = الوتد C

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

في هذه المرحلة:

المصدر = الوتد أ
الوجهة = الربط ب
المساعد = الوتد C

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

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

في هذه المرحلة:

المصدر = الوتد أ
الوجهة = الربط C
مساعد = ربط ب

الخطوة 7) الآن يمكننا أن نرى ذلك

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

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

في هذه المرحلة:

المصدر = الربط ب
الوجهة = الوتد أ
المساعد = الوتد C

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

في هذه المرحلة:

المصدر = الربط ب
الوجهة = الربط C
المساعد = الوتد أ

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

في هذه المرحلة:

المصدر = الوتد أ
الوجهة = الربط C
مساعد = ربط ب

الكود الزائف لبرج هانوي

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 دالة متكررة للقرص مرتين.
يمكن أن يتحرك القرص 1 خلال وقت ثابت، والوقت لحل ثلاثة أقراص.

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

= 2*(2*الوقت اللازم لحل قرص واحد + الوقت الثابت لنقل القرص 2) + الوقت الثابت لنقل القرص 3

= (2*2) (الوقت الثابت لنقل القرص 1) + 2*الوقت الثابت لنقل القرص 2 + الوقت الثابت لنقل القرص 3

بالنسبة للأقراص n، يمكن كتابتها بالشكل -

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

سيؤدي هذا التقدم الهندسي إلى O(2^N-1) أو يا (2ⁿ), وهو الأسي.

2) تعقيد الفضاء

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

قد ترغب:

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

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

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

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

ذات المواد

الكود الزائف لبرج هانوي

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

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

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