Ханойские башни

На одном из трех алмазных шпилей надето 64 круглых золотых диска.

Ханойские башни

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

  • за один раз можно перемещать только один диск;
  • больший диск нельзя располагать на меньшем диске;
  • снятый диск необходимо надеть на какой-либо шпиль перед тем, как будет снят другой диск.

Трудолюбивые буддийские монахи день и ночь переносят диски со шпиля на шпиль. Легенда утверждает, что когда монахи закончат свою работу, наступит конец света. Можно легко подсчитать, что для решения задачи с 64 дисками потребуется 264-1 перемещений (около 1020). Поэтому, что касается конца света, то он произойдет по истечении пяти миллиардов веков, если считать, что один диск перемещается за одну секунду. Впрочем, и задачу, и легенду для неё придумал в 1883 году математик Э. Люка. Это дает нам право отложить заботы о конце света в сторону и перейти к решению следующей задачи.

Задача. Составьте рекурсивную программу, которая бы решала поставленную выше задачу о Ханойских башнях при количестве дисков, равном n  (n = 1, 2, …).

Технические требования

Пронумеруем шпили справа налево 1, 2, 3. В начале все диски расположены на шпиле номер 1. В результате работы программы на экран выводится последовательность пар чисел (переносов дисков). Первое число в паре — номер шпиля, с которого сняли диск, второе число — номер шпиля, куда диск надели.

Вариант усложнённый

Показывать анимационно правильное перемещение дисков.

Пример

n= 3
1 2
1 3
2 3
1 2
3 1
3 2
1 2

Можно попробовать поиграть в эту игру здесь.

 

 

Добавить комментарий