УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Биоинформатика
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Нейронные сети
 ФЦП ИТМО-Аалто
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



   Главная / Статьи / Ханойские башни и автоматы (версия для печати)


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



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

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

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

Аннотация

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

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

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

Литература

  1. Седжвик Р. Фундаментальные алгоритмы на С++. Киев: ДиаСофт, 2001.
  2. Грэхем Р., Кнут Д., Поташник О. Конкретная математика. М.: Мир, 1998.
  3. Романовский И.В., Столяр С.Е. Стек и его использование. http://ips.ifmo.ru
  4. Гарднер М. Математические головоломки и развлечения. М.: Мир, 1971.
  5. Бобак И. Алгоритмы: "возврат назад" и "разделяй и влавствуй" //Программист. 2002. №3.
  6. Шалыто А.А., Туккель Н.И. От тьюрингова программирования к автоматному //Мир ПК. 2002. №2.
  7. Стивенс Р. Delphi. Готовые алгоритмы. М.: ДМК, 2001.
  8. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000.



© 2002—2017 По техническим вопросам сайта: vl.ulyantsev@gmail.com