Процедура БАШНЯ

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

Выполненные таким образом семь

шагов завершают выполнение первой процедуры БАШНЯ на втором уровне диаграммы, и компьютер продолжает действовать в той же манере, то опускаясь к табличкам нижних уровней, то возвращаясь на более высокий уровень. В конце концов программа проходит по всей диаграмме и задача оказывается решенной.

Эффект рекурсии воспринимается иногда как некое волшебство, потому что все многочисленные записи для запоминания, «где мы находимся», делаются компьютером — человеку трудно запомнить такой большой объем информации. Однако существует другой мтод решения. Четыре года назад П. Бьюне- ману из Университета шт. Пенсильвания и J1. Леви из AT&T Bell Laboratories удалось найти простую последовательность перемещений, позволяющих решить задачу о башне. Бьюнеман и Леви предложили воспользоваться простым чередованием перемещений двух видов:

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

2.  Перенести любой диск, кроме наименьшего.

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

Не так давно я сделал из дерева все необходимое для задачи о башне с восемью дисками и предложил одному своему знакомому «поиграть». У него ничего не получилось и он вышел из комнаты. Тем временем я быстро объяснил алгоритм решения Бьюнема- на — Леви его восьмилетней дочери, которая до этого наблюдала за игрой как зачарованная. Когда мой друг вернулся, он был поражен, видя как его дочь спокойно без малейшего колебания перекладывает диски со стержня на стержень. Через несколько минут она решила задачу. «Ну и ребенок у тебя», — сказал я.

 

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

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

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