كيفية حل مشكلة برج هانوي - دليل خوارزمية مصور

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

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

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

قبل أن نتمكن من الوصول إلى هناك ، لنتخيل أن هناك نقطة وسيطة ب .

يمكننا استخدام B كمساعد لإنهاء هذه المهمة. نحن الآن جاهزون للمضي قدما. دعنا ننتقل إلى كل خطوة من الخطوات:

  1. انقل القرص الأول من A إلى C.
  2. انقل القرص الأول من أ إلى ب
  3. انقل القرص الأول من C إلى B.
  4. انقل القرص الأول من A إلى C.
  5. انقل القرص الأول من B إلى A.
  6. انقل القرص الأول من B إلى C.
  7. انقل القرص الأول من A إلى C.

فقاعة! لقد حللنا مشكلتنا.

يمكنك رؤية الصورة المتحركة أعلاه لفهم أفضل.

الآن ، دعنا نحاول بناء الخوارزمية لحل المشكلة. انتظر ، لدينا كلمة جديدة هنا: " الخوارزمية ". ما هذا؟ اي فكرة؟ لا مشكلة ، دعنا نرى.

ما هي الخوارزمية؟

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

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

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

في الرياضيات وعلوم الكمبيوتر ، تعد الخوارزمية تحديدًا لا لبس فيه لكيفية حل فئة من المشكلات. يمكن للخوارزميات أداء مهام الحساب ومعالجة البيانات والاستدلال الآلي. - ويكيبيديا

إذا ألقيت نظرة على هذه الخطوات ، يمكنك أن ترى أننا كنا نقوم بنفس المهمة عدة مرات - نقل الأقراص من مكدس إلى آخر. يمكننا استدعاء هذه الخطوات داخل الخطوات العودية .

العودية

العوديةيستدعي نفس الإجراء من هذا الإجراء. تماما مثل الصورة أعلاه.

لذلك هناك قاعدة واحدة للقيام بأي عمل تكراري: يجب أن يكون هناك شرط لإيقاف تنفيذ هذا الإجراء. أتمنى أن تفهم الأساسيات حول العودية.

الآن ، دعنا نحاول بناء إجراء يساعدنا في حل مشكلة برج هانوي. نحن نحاول بناء الحل باستخدام pseudocode . Pseudocode هي طريقة لكتابة كود الكمبيوتر باستخدام اللغة الإنجليزية.

tower(disk, source, intermediate, destination) { }

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

الآن نحن بحاجة إلى إيجاد حالة نهائية . الحالة النهائية هي الحالة التي لن نطلق عليها هذه الوظيفة بعد الآن.

IF disk is equal 1

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

حسنًا ، لقد وجدنا نقطة الحالة الطرفية حيث ننقل قرصنا إلى الوجهة كما يلي:

move disk from source to destination

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

tower(disk - 1, source, destination, intermediate)

كما قلنا ، نجتاز total_disks_on_stack - 1 كوسيطة. ثم مرة أخرى نقوم بتحريك قرصنا مثل هذا:

move disk from source to destination

بعد ذلك نسمي طريقتنا مرة أخرى مثل هذا:

tower(disk - 1, intermediate, source, destination)

دعنا نرى كودنا الكاذب الكامل:

tower(disk, source, inter, dest) IF disk is equal 1, THEN move disk from source to destination ELSE tower(disk - 1, source, destination, intermediate) // Step 1 move disk from source to destination // Step 2 tower(disk - 1, intermediate, source, destination) // Step 3 END IF END

هذه الشجرة لثلاثة أقراص:

هذا هو الكود الكامل في روبي:

def tower(disk_numbers, source, auxilary, destination) if disk_numbers == 1 puts "#{source} -> #{destination}" return end tower(disk_numbers - 1, source, destination, auxilary) puts "#{source} -> #{destination}" tower(disk_numbers - 1, auxilary, source, destination) nil end

مكالمة tower(3, 'source','aux','dest')

انتاج:

source -> dest source -> aux dest -> aux source -> dest aux -> source aux -> dest source -> dest

استغرق الأمر سبع خطوات لثلاثة أقراص للوصول إلى الوجهة. نسمي هذه الطريقة العودية .

تعقيد الوقت وحسابات تعقيد المكان

تعقيد الوقت

عندما نقوم بتشغيل كود أو تطبيق في أجهزتنا ، يستغرق الأمر وقتًا - دورات وحدة المعالجة المركزية. لكنها ليست نفسها لكل جهاز كمبيوتر. على سبيل المثال ، فإن وقت المعالجة لكل من Core i7 و Dual Core ليس هو نفسه. لحل هذه المشكلة ، يوجد مفهوم مستخدم في علوم الكمبيوتر يسمى تعقيد الوقت .

تعقيد الوقت هو مفهوم في علوم الكمبيوتر يتعامل مع التقدير الكمي لمقدار الوقت الذي تستغرقه مجموعة من التعليمات البرمجية أو الخوارزمية للمعالجة أو التشغيل كدالة لمقدار المدخلات.

In other words, time complexity is essentially efficiency, or how long a program function takes to process a given input. — techopedia

The time complexity of algorithms is most commonly expressed using big O notation. It’s an asymptotic notation to represent the time complexity.

Now, the time required to move n disks is T(n). There are two recursive calls for (n-1). There is one constant time operation to move a disk from source to the destination, let this be m1. Therefore:

T(n) = 2T(n-1) + m1 ..... eq(1)

And

T(0) = m2, a constant ...... eq(2) From eq (1) T(1) = 2T(1-1) + m1 = 2T(0)+m1 = 2m2 + m1 ..... eq(3) [From eq 2] T(2) = 2T(2-1) + m1 = 2T(1) + m1 = 4m2 + 2m1 + m1 .... eq(4) [From eq(3)] T(3) = 2T(3-1) + m1 = 2T(2) + m1 = 8m2 + 4m1 + 2m1 + m1 [From eq(4)]

From these patterns — eq(2) to the last one — we can say that the time complexity of this algorithm is O(2^n) or O(a^n) where a is a constant greater than 1. So it has exponential time complexity. For the single increase in problem size, the time required is double the previous one. This is computationally very expensive. Most of the recursive programs take exponential time, and that is why it is very hard to write them iteratively.

Space complexity

After the explanation of time complexity analysis, I think you can guess now what this is…This is the calculation of space required in ram for running a code or application.

In our case, the space for the parameter for each call is independent of n,meaning it is constant. Let it be J. When we do the second recursive call, the first one is over. That means that we can reuse the space after finishing the first one. Hence:

T(n) = T(n-1) + k .... eq(1) T(0) = k, [constant] .... eq(2) T(1) = T(1-1) + k = T(0) + k = 2K T(2) = 3k T(3) = 4k

So the space complexity is O(n).

After these analyses, we can see that time complexity of this algorithm is exponential but space complexity is linear.

Conclusion

From this article, I hope you can now understand the Tower of Hanoi puzzle and how to solve it. Also, I tried to give you some basic understanding about algorithms, their importance, recursion, pseudocode, time complexity, and space complexity. If you want to learn these topics in detail, here are some well-known online courses links:

  1. Algorithms, Part I
  2. Algorithms, Part II
  3. دورة Google على Udacity
  4. اعتماد خوارزميات جافا سكريبت وهياكل البيانات (300 ساعة)

يمكنك زيارة هياكل البيانات الخاصة بي وإعادة الخوارزمياتلرؤية حلول مشاكلي الأخرى.

أنا على جيثب | تويتر | ينكدين