Ханойские башни и автоматы

Статья опубликована в журнале "Программист", 2002. №8. C.82-90.

Анатолий Шалыто, Никита Туккель, Никита Шамгунов

Отсюда можно скачать полный текст статьи в формате pdf (191 кб)

Аннотация

Одной из наиболее известных рекурсивных задач является задача о ханойских башнях [1-5], которая формулируется следующим образом. Имеются три стержня, на первом из которых размещено N дисков. Диск наименьшего диаметра находится сверху, а ниже - диски последовательно увеличивающегося диаметра. Задача состоит в определении последовательности перекладываний по одному диску со стержня на стержень, которые должны выполняться так, чтобы диск большего диаметра никогда не размещался выше диска меньшего диаметра и чтобы, в конце концов, все диски оказались на другом стержне.

В рассматриваемой работе показано, что применение автоматов [6] позволяет формально переходить к итеративным алгоритмам решения этой задачи, либо строить такие алгоритмы непосредственно. В работах [7,8] приведены примеры преобразований рекурсивных программ в итеративные, однако подходы, обеспечивающие такие преобразования, не формализованы. Настоящая работа призвана устранить этот пробел.

В статье предлагаются три метода. Первый из них обеспечивает формальное построение автоматной программы (программы, построенной с использованием автоматов) на основе раскрытия рекурсии с применением стека. Второй метод также обеспечивает раскрытие рекурсии и состоит в построении автомата, осуществляющего обход дерева действий, выполняемых рекурсивной программой. Третий метод состоит в непосредственном управлении стержнями с помощью автомата и не использует таких абстракций как деревья и стеки. Отметим, что применение каждого из предлагаемых методов для рассматриваемой задачи порождает автоматы с двумя или тремя состояниями, управляющие "объектом управления" с 2^N состояниями, возникающими в процессе перекладывания дисков.

Литература

1. Седжвик Р. Фундаментальные алгоритмы на С++. Киев: ДиаСофт, 2001.

2. Грэхем Р., Кнут Д., Поташник О. Конкретная математика. М.: Мир, 1998.

3. Романовский И.В., Столяр С.Е. Стек и его использование. http://ips.ifmo.ru.

4. Гарднер М. Математические головоломки и развлечения. М.: Мир, 1971.

5. Бобак И. Алгоритмы: "возврат назад" и "разделяй и влавствуй" //Программист. 2002. №3.

6. Шалыто А.А., Туккель Н.И. От тьюрингова программирования к автоматному //Мир ПК. 2002. №2.

7. Стивенс Р. Delphi. Готовые алгоритмы. М.: ДМК, 2001.

8. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000.