Основы программирования на C++, PASCAL

5.3. Рекурсивные методы

Суть рекурсивных методов — сведение задачи к самой себе. Вы уже знаете, что как в Паскале, так и в Си существует возможность рекурсивного определения функций и процедур. Эта возможность представляет собой способ программной реализации рекурсивных алгоритмов. Однако увидеть рекурсивный путь решения задачи (рекурсивный алгоритм) часто очень непросто.

Рассмотрим классическую задачу, известную в литературе под названием «Ханойская башня» (рис. 50).

На площадке (назовем ее А) находится пирамида, составленная из дисков уменьшающегося от основания к вершине размера.

Эту пирамиду в том же виде требуется переместить на площадку В. При выполнении этой работы необходимо соблюдать следующие ограничения:

• перекладывать можно только по одному диску, взятому сверху пирамиды;

• класть диск можно либо только на основание площадки, либо на диск большего размера;

• в качестве вспомогательной можно использовать площадку С.

Название «Ханойская башня» связано с легендой, согласно которой в давние времена монахи одного ханойского храма взялись переместить по этим правилам башню, состоящую из 64 дисков. С завершением их работы наступит конец света. Монахи все еще работают и, надеемся, еще долго будут работать!

Нетрудно решить эту задачу для двух дисков. Обозначая перемещения диска, например, с площадки А на В так: А → В, напишем алгоритм для этого случая

А→С; А→В; С→В.

Всего 3 хода! Для трех дисков алгоритм длиннее:

А→В; А→С; В→С; А→В; С→А; С→В; А→В.

В этом случае уже требуются 7 ходов.

Подсчитать количество ходов (N) для k дисков можно по следующей рекуррентной формуле:

N(1) = 1; N(k) = 2х N(k - 1) + 1.

Например, N(10) = 1023, N(20) = 104857. А вот сколько перемещений нужно сделать ханойским монахам:

N(64) = 18446744073709551615.

Попробуйте прочитать это число.

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

1. Если п = 0, то ничего не делать.

2. Если п > 0, то   переместить п — 1 диск на С через В;

переместить диск с А на В (А → В)

переместить п — 1 диск с С на В через А.

При выполнении пункта 2 последовательно будем иметь три состояния (рис. 51).

Описание алгоритма имеет явно рекурсивный характер