Программы для задачи о башне

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

Предположим, что нужно переместить пять дисков со стержня А (исходный) на стержень В (конечный). Если вместо п подставить число 5, а вместо слов «исходный», «конечный» и «вспомогательный» соответственно буквы А, В и С, то рассматриваемую процедуру можно переписать в таком виде:

БАШНЯ (5. А – В):

БАШНЯ (4, А – С)

ПЕРЕНОС (5,А – В)

БАШНЯ (4, С – В)

Другими словами, программа должна сначала справиться с задачей перемещения первых четырех дисков со стержня А на стержень С. Далее, согласно нашей алгоритмической записи, когда эта процедура завершена, нужно выполнить ПЕРЕНОС (5, А — В), т.е. перенести пятый, наибольший диск со стержня А на стержень В. Затем следует еще одно обращение к процедуре БАШНЯ для того, чтобы переместить первые четыре диска со стержня С на стержень В.

Каждое обращение к процедуре БАШНЯ влечет за собой еще три обращения к процедурам: БАШНЯ, затем ПЕРЕНОС и снова БАШНЯ. Процедура ПЕРЕНОС не может быть выполнена, пока не завершена первая процедура БАШНЯ. Это означает, что порядок действий, выполняемых компьютером, следующий: сначала четыре раза подряд выполняется процедура БАШНЯ; при этом мы перемещаемся вниз влево по диаграмме, пока не приходим к последовательности

БАШНЯ (I, А – В)

ПЕРЕНОС (2, А – О БАШНЯ И, В – О

Реальная программа должна будет содержать одну дополнительную команду. Когда остается только один диск в процедуре БАШНЯ, он переносится непосредственно со стержня на стержень без использования рекурсии. Первый диск переносится со стержня А на стержень В. Затем с помощью процедуры ПЕРЕНОС второй диск перемещается со стержня А на стержень С. Наконец, компьютер снова «переносит» первый диск, на этот раз со стержня В на стержень С.

 

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

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

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