Як вирішити проблему вежі Ханоя - Ілюстрований посібник з алгоритму

Перш ніж розпочати, давайте поговоримо про те, в чому проблема Ханойської вежі. Ну, це весела гра-головоломка, метою якої є переміщення цілої стопки дисків з вихідної позиції в іншу позицію. Дотримуються трьох простих правил:

  1. Одночасно можна переміщати лише один диск.
  2. Кожен хід складається з того, щоб взяти верхній диск з однієї з стопок і покласти його поверх іншої стопки. Іншими словами, диск можна переміщати лише в тому випадку, якщо це самий верхній диск у стеку.
  3. Більший диск не можна розміщувати поверх меншого диска.

Тепер спробуємо уявити сценарій. Припустимо, у нас є стек з трьох дисків. Наша робота полягає в тому, щоб перемістити цей стек з джерела А для призначення C . Як ми це робимо?

Перш ніж ми зможемо потрапити туди, давайте уявимо , є проміжна точка B .

Ми можемо використовувати B як помічника, щоб закінчити цю роботу. Зараз ми готові рухатися далі. Давайте пройдемо кожен із етапів:

  1. Перемістіть перший диск з А в С
  2. Перемістіть перший диск з А в В
  3. Перемістіть перший диск з C на B
  4. Перемістіть перший диск з А в С
  5. Перемістіть перший диск з B в A
  6. Перемістіть перший диск з B на C
  7. Перемістіть перший диск з А в С

Бум! Ми вирішили свою проблему.

Ви можете побачити анімоване зображення вище для кращого розуміння.

Тепер спробуємо побудувати алгоритм вирішення проблеми. Зачекайте, у нас тут нове слово: “ Алгоритм ”. Що це? Будь-яка ідея? Не біда, подивимось.

Що таке алгоритм?

Алгоритм - одне з найважливіших понять для розробника програмного забезпечення. Насправді, я думаю, що це важливо не лише для розробки програмного забезпечення чи програмування, але й для всіх. Алгоритми впливають на нас у повсякденному житті. Подивимось як.

Припустимо, ви працюєте в офісі. Тож щоранку ви виконуєте ряд завдань у послідовності: спочатку прокидаєтесь, потім ви йдете до умивальника, снідаєте, готуєтесь до офісу, виїжджаєте з дому, потім можете сісти на таксі або автобус або почати йти до і через певний час ви дійдете до свого офісу. Ви можете сказати, що всі ці кроки утворюють алгоритм .

Простіше кажучи, алгоритм - це сукупність завдань. Сподіваюся, ви не забули тих кроків, які ми зробили, щоб перенести стек трьох дисків з А на С. Ви також можете сказати, що ці кроки є алгоритмом вирішення проблеми Вежі Ханоя.

У математиці та інформатиці алгоритм - це однозначна специфікація способу вирішення класу задач. Алгоритми можуть виконувати завдання обчислення, обробки даних та автоматизованих міркувань. - Вікіпедія

Якщо ви подивитесь на ці кроки, ви побачите, що ми виконували одне і те ж завдання кілька разів - переміщуючи диски з одного стека в інший. Ми можемо назвати ці кроки всередині кроків рекурсією .

Рекурсія

Рекурсіявикликає ту саму дію з цієї дії. Так само, як наведене вище зображення.

Отже, є одне правило для виконання будь-якої рекурсивної роботи: повинна бути умова, щоб зупинити виконання цієї дії. Сподіваюся, ви розумієте основи рекурсії.

Тепер спробуємо побудувати процедуру, яка допоможе нам вирішити проблему Вежі Ханоя. Ми намагаємось створити рішення за допомогою псевдокоду . Псевдокод - метод виписування комп’ютерного коду з використанням англійської мови.

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

Це скелет нашого рішення. В якості аргументу беремо загальну кількість дисків. Потім нам потрібно передати джерело, проміжне місце та пункт призначення, щоб ми могли зрозуміти карту, яку ми будемо використовувати для завершення роботи.

Тепер нам потрібно знайти стан терміналу . Термінальний стан - це стан, коли ми більше не збираємося викликати цю функцію.

IF disk is equal 1

У нашому випадку це буде наш термінальний стан. Тому що, коли в нашому стеку буде один диск, тоді просто зробити цей останній крок, і після цього наше завдання буде виконано. Не хвилюйтеся, якщо вам це не зрозуміло. Коли ми дійдемо до кінця, ця концепція буде зрозумілішою.

Добре, ми знайшли свою точку стану терміналу, куди ми переміщаємо наш диск до місця призначення так:

move disk from source to destination

Тепер ми знову викликаємо нашу функцію, передаючи ці аргументи. У цьому випадку ми ділимо стос дисків на дві частини. Найбільший диск ( n-й диск) знаходиться в одній частині, а всі інші ( n-1 ) диски - у другій частині. Там ми називаємо метод два рази для - (n-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

Це дерево для трьох дисків:

Це повний код в Ruby:

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

Потрібно було сім кроків, щоб три диски дійшли до місця призначення. Ми називаємо це рекурсивним методом .

Розрахунки часової та просторової складності

Складність часу

Коли ми запускаємо код або додаток на нашій машині, потрібен час - цикли процесора. Але це не однаково для кожного комп’ютера. Наприклад, час обробки для ядра i7 і двоядра не є однаковим. Для вирішення цієї проблеми в інформатиці використовується концепція, яка називається часовою складністю .

Складність часу - це поняття в інформатиці, яке має справу з кількісною оцінкою кількості часу, затраченого набором коду або алгоритму на обробку чи запуск як функцію кількості вхідних даних.

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. The Google course on Udacity
  4. Javascript Algorithms And Data Structures Certification (300 hours)

You can visit my data structures and algorithms repoto see my other problems solutions.

I am on GitHub | Twitter | LinkedIn