Структура данных и алгоритмы - Ханойская башня

Ханойская башня, это математическая головоломка, которая состоит из трех башен (колышков) и более одного кольца, как изображено -

Ханойская башня

Эти кольца имеют разные размеры и сложены в порядке возрастания, то есть меньшее расположено над большим. Существуют и другие варианты головоломки, в которых количество дисков увеличивается, но количество башен остается неизменным.

правила

Миссия состоит в том, чтобы переместить все диски в какую-то другую башню, не нарушая последовательность расположения. Вот несколько правил, которым нужно следовать для Ханойской башни:

  • Только один диск может быть перемещен среди башен в любой момент времени.
  • Только «верхний» диск может быть удален.
  • Ни один большой диск не может сидеть над маленьким диском.

Ниже приводится анимационное изображение решения головоломки Ханойской башни с тремя дисками.

Ханойская башня

Загадка Ханойской башни с n дисками может быть решена минимум за 2 n −1 шагов. Эта презентация показывает, что головоломка с 3 дисками прошла 2 3 - 1 = 7 шагов.

Алгоритм

Чтобы написать алгоритм для Ханойской башни, сначала нам нужно узнать, как решить эту проблему с меньшим количеством дисков, скажем, → 1 или 2. Мы помечаем три башни с именем, источником , местом назначения и вспомогательным (только для перемещения дисков ). Если у нас есть только один диск, он может быть легко перемещен из исходной точки в точку привязки.

Если у нас есть 2 диска -

  • Сначала мы перемещаем меньший (верхний) диск в вспомогательную привязку.
  • Затем мы перемещаем больший (нижний) диск в целевой колышек.
  • И, наконец, мы перемещаем меньший диск из вспомогательной в конечную привязку.
Ханойская башня с двумя дисками

Итак, теперь мы можем разработать алгоритм для Ханойской башни с более чем двумя дисками. Разобьем стек дисков на две части. Самый большой диск (n- й диск) находится в одной части, а все остальные (n-1) - во второй части.

Наша конечная цель - переместить диск n из источника в место назначения и затем поместить на него все остальные (n1) диски. Мы можем представить, чтобы применить это рекурсивным способом для всего данного набора дисков.

Следующие шаги -

 Step 1 − Move n-1 disks from source to aux
Step 2 − Move n th disk from source to dest
Step 3 − Move n-1 disks from aux to dest

Рекурсивный алгоритм для Ханойской башни может быть реализован следующим образом:

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Чтобы проверить реализацию в C-программировании, нажмите здесь .