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

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

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

Правила

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

Между башнями в любой момент времени можно перемещать только один диск.
Снимать можно только «верхний» диск.
Никакой большой диск не может поместиться поверх маленького.

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

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

Алгоритм

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

Если у нас 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, щелкните здесь .