|
Н.И. Туккель, А.А. Шалыто, Н.Н. Шамгунов
Статья опубликована в журнале "Телекоммуникации и информатизация образования", 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
|