Ключ к построению решения задачи

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

1.  Перенести башню из л — 1 дисков с исходного стержня на вспомогательный.

2.  Переложить л-й диск с исходного стержня на конечный.

3.  Снова перенести башню из л — 1 дисков — на этот раз со вспомогательного стержня на конечный.

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

воспользоваться последовательностью шагов для того, чтобы перенести башню из л — 1 дисков с исходного стержня на вспомогательный. На следующей стадии л-й диск, освобожденный от лежавших на нем меньших дисков, перекладывается на конечный стержень. На третьей стадии можно снова воспользоваться решением задачи для л — 1 дисков, чтобы переместить их со вспомогательного стержня на конечный.

Рассмотренный процесс решения с многочисленными «ветвями» и «под- ветвями» для человека кажется очень запутанным, однако теперь нам становится ясно, почему для решения такой задачи требуется почти 2" шага: при. каждом использовании процедуры она дважды повторяет сама себя. И если человеку трудно себе представить, как можно реализовать подобную процедуру решения, для компьютера это не вызывает никаких затруднений.

Рисунок внизу показывает часть решения задачи с пятью дисками. Три стадии, рассмотренные нами выше, представлены как процедуры, встроенные в ббльшую процедуру с именем БАШНЯ (л, X — К). В этой процедуре используются три элемента данных: л — число дисков, которые нужно переместить, X — исходный стержень и Y — конечный стержень.

 

0 Коментариев

Вы можете быть первым =)

Оставить коментарий