Рассмотрим следующую весьма популярную у студентов задачу.

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

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

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

Решение. Введем имена для шпилей: a, b, c. Пусть hanoi(n,a,b,c) - искомая функция, возвращающая последовательность перемещений дисков с a на b c использованием c по вышеописанным правилам. При n=1 решать задачу мы умеем. Необходимо просто произвести операцию “переместить a ® b”. Предположим, что мы умеем решать эту задачу для n – 1 диска. Тогда общая схема рекурсии могла бы выглядеть следующим образом:

Иными словами, переместим n–1 диск с a на с. Далее, переместим один оставшийся диск с a на b и, наконец, переместим n–1 диск с c на b. Что нам мешает реализовать эту схему на языке программирования Mathcad? По-видимому, то, что в процессе вычисления функции hanoi(n,a,b,c) мы не в состоянии организовать вывод сообщений типа “переместить a ® b”. Остается одно средство - организовать рекурсивные обращения так, чтобы все подобные ходы-перемещения запоминались в массиве, который и будет возвращаться функцией hanoi(n,a,b,c).

Вот один из возможных вариантов определения функции hanoi():

Функция возвращает матрицу размера k´2, в каждой строчке которой фиксируется перемещение одного диска (откуда, куда). Величина k равна общему количеству перемещений.

Контрольный пример. При трех дисках с именами шпилей 1, 2 и 3 получаем следующее решение: