Пример рекурс алгоритмаЗадача о Ханойских башнях.

Отображение более сложных рекурсивных связей в алгоритмах покажем на примере задачи о Ханойских башнях. Эта интересная задача была сформулирована в 1883 году математиком Э.Люка. Многие учебные пособия по программированию используют ее как классический пример рекурсивного алгоритма.

Суть задачи состоит в следующем. Где-то далеко в окрестностях города Ханой стоят три башни. Одна из башен состоит из 97 золотых дисков, положенных друг на друга - как кольца в детской пирамиде. Диаметры всех дисков различны и уменьшаются от нижнего к верхнему. Необходимо перенести все диски с одной башни на другую. При этом диски можно переносить только по одному с любой башни на другую. Ставить диск на землю или надевать больший на меньший нельзя! Согласно легенде этой работой заняты монахи

из местного монастыря. День и ночь они заняты переносом дисков с башни на башню. Когда они закончат всю работу - наступит конец света. Кстати, это вполне похоже на правду: для перемещения N дисков на другой стержень (по одному, не кладя больший на меньший) нужно сделать 2n-1 перемещений, что легко следует по индукции.

Для определения подхода к решению поставленной задачи, рассмотрим общий случай с п дисками. Если мы сможем сформулировать решение для п дисков в терминах решения для n-1 диска, то поставленная проблема была бы решена, поскольку задачу для n-1 диска можно будет, в свою очередь, решить в терминах n-2 дисков и так далее до тривиального случая одного диска. А для случая одного диска решение получается элементарным. Нужно просто переместить один единственный диск со столбика А на столбик С.

Таким образом, если сформулировать решение для п дисков в терминах п-1 диска, то мы фактически получим алгоритм рекурсивной процедуры, с помощью которой можно легко достичь цели поставленной задачи. Рассмотрим словесное описание алгоритма. Если n=1, тогда переместить этот диск со столбика А на столбик С и остановиться. В противном случае, надо поступить следующим образом: 1. переместить верхние n-1 диск со столбика А на столбик В, используя столбик С как вспомогательный. 2. переместить оставшийся нижний диск со столбика А на столбик С. 3. переместить п-1 диск со столбика В на столбик С, используя столбик А как вспомогательный.

Можно с уверенностью сказать, что т акая последовательность действий даст корректное решение для любого значения п. Это вытекает из следующего. Если n=1, то корректность очевидна. Если n=2, то мы знаем, что уже имеем решение для случая (n-l)-ro диска, которое равно 1. аналогично, если n=3, мы снова имеем решение для (n-l)-ro диска, которое равно 2 и т.д.

Программа, которая решает поставленную задачу с помощью рекурсивной процедуры.

Дата добавления: 2015-07-16