Ханойская башня: рекурсивный алгоритм

Я согласен, что это не сразу, когда вы впервые смотрите на него, но это довольно просто, когда вы дойдете до него.

Базовый случай: ваша башня имеет размер 1. Таким образом, вы можете сделать это за один ход, от источника прямо к месту назначения.

Рекурсивный случай: ваша башня имеет размер n > 1. Таким образом, вы перемещаете верхнюю башню размера n-1 на дополнительный колышек (на), перемещаете нижнюю "башню" размера 1 на целевой колышек и перемещаете верхнюю башню от точки на место назначения.

в простом случае у вас есть башня высотой 2:

 _|_    |     |
__|__   |     |
===== ===== =====

Первый шаг: переместите верхнюю башню 2-1 (= 1) на дополнительный колышек (допустим, средний).

  |     |     |
__|__  _|_    |
===== ===== =====

Далее: переместите нижний диск к месту назначения:

  |     |     |
  |    _|_  __|__
===== ===== =====

И, наконец, переместите верхнюю башню (2-1) = 1 к месту назначения.

  |     |    _|_
  |     |   __|__
===== ===== =====

Если подумать,даже если башен было 3 или больше, всегда будет пустой дополнительный стержень или стержень со всеми большими дисками, который будет использоваться рекурсией при замене башен местами.

Это просто.

Как студент, изучающий компьютерные науки, вы, возможно, слышали о математической индукции. Рекурсивное решение для Ханойской башни работает аналогично - только другая часть состоит в том, чтобы действительно не потеряться с B и C, как если бы закончилась полная башня.

Первый рекурсивный вызов перемещает все части, кроме самой большой, из источника в, используя dest в качестве вспомогательной стопки. Когда закончите, все части, кроме самой большой, будут лежать рядом, а самая большая свободна. Теперь вы можете переместить самую большую часть в dest и использовать другой рекурсивный вызов для перемещения всех частей из by в dest.

Рекурсивные вызовы ничего не знают о самой большой части (т.е. они проигнорируют ее), но это нормально потому что рекурсивные вызовы будут иметь дело только с меньшими частями и, таким образом, могут свободно перемещаться на самую большую часть и с нее.

Хорошее объяснение рекурсивной реализации Ханоя можно найти на http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html . 12114] Резюме: если вы хотите переместить нижнюю пластину с ручки A на стержень B, вам сначала нужно переместить все меньшие пластины поверх нее из точки A в C. Второй рекурсивный вызов - затем переместить пластины, которые вы переместили. в C обратно на B после того, как ваш базовый вариант переместил одну большую пластину из A в B.

Год назад я прошел курс функционального программирования и нарисовал эту иллюстрацию для алгоритма. надеюсь, что это поможет!

(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (B -> C)



(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)



(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)

Задача трех колец была разделена на задачу 2 двух колец (1.x и 3.x)