SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Учебный процесс
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


Реализация рекурсивных алгоритмов на основе автоматного подхода

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

Статья опубликована в журнале "Телекоммуникации и информатизация образования", 2002, № 5.

Статья в формате pdf (~180 кб)

Аннотация

В работе [1] предложен метод преобразования произвольных итеративных программ в автоматные программы, что позволяет реализовать произвольный итеративный алгоритм структурированной программой, содержащей один оператор do-while, телом которого является один оператор switch.

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

В настоящей работе такой метод предлагается. Он состоит в преобразовании заданной программы с явной рекурсией в итеративную программу, построенную с использованием автомата Мили. Такие программы, как и в работе [1], будем называть автоматными. Метод иллюстрируется примерами преобразований классических рекурсивных программ, которые приведены в порядке их усложнения (факториал, числа Фибоначчи, ханойские башни, задача о ранце).

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

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

Литература

1. Шалыто А.А., Туккель Н.И. Преобразование итеративных алгоритмов в автоматные //Программирование. 2002. №5. (http://is.ifmo.ru, раздел "Статьи")

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

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

С авторами можно связаться по адресу: Shalyto@mail.ifmo.ru