Разное

Сервис

Психология автоматного программирования

[ <<< | 1 | 2 | 3 | Литература | Приложение | >>> ]

© Б.П. Кузнецов

Конкретный пример

Возможно, читатель понял не все из сказанного, поэтому перейдем от абстрактного примера к конкретной работающей программе.

Задача ставится следующим образом. Даны два массива. Каждый из них содержит последовательность неповторяющихся чисел, завершающуюся нулем. Второй массив содержит ту же, что и в первом, последовательность, но включает вставки из чисел, отсутствующих в первом массиве. Например:

М1 = 2 4 5 7 8 9 12 13 0

М2 = 2 4 5 21 23 24 7 8 9 12 13 0

(подчеркнута вставка).

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

Данная задача имеет практический интерес, например, для выявления различий в исходных текстах программ, с заменой операций сравнения чисел операциями сравнения строк текстов. (Удаления и замены мы намеренно не рассматриваем, чтобы не перегружать пример.)

Массивы обозначим m1 и m2, а номера их элементов, соответственно, s1 и s2.

Программу будем реализовывать как подпрограмму с единственным циклом while, управляемым переменной cycle. После вызова подпрограммы устанавливаем переменную cycle в единицу и входим в цикл while(cycle), где и сосредоточены все операторы.

Задачу будем решать последовательным добавлением вершин графа переходов. На рис. 2 показан первый шаг такого построения, где в объемлющем прямоугольнике, изображающем цикл while(cycle), показано начальное состояние А программы, связанное переходами с неуказанными пока локальными событиями и действиями на переходе с прямоугольником, обозначенным знаком вопроса, и отождествляемого с неизвестными пока состояниями. Очевидно, по крайней мере одно действие на переходе (возврате) из неизвестных состояний в начальное, а именно: cycle = 0 – в обеспечение завершения программного цикла while(cycle) и выхода из программы. Итак, наша программа вошла в начальное состояние и в следующем проходе цикла переходит в новое, пока не известное, состояние.

Выполним второй шаг (рис. 3), то есть добавим новое состояние В. В этом состоянии будем сравнивать элементы двух массивов. Очевидно, что, пока последовательности совпадают сравниваемые элементы равны. Поэтому состояние В назовем состоянием ожидания вставки, или неравенства очередных элементов массивов. В этом состоянии будет модификация – приращение номеров элементов массивов на единицу (s1++; s2++; - см. прямоугольник В на рис. 3). В обеспечение первой такой модификации зададим начальное значение s1 = s2 = -1, которое и установим на переходе из начального состояния ‘А’ в состояние ‘В’. Модификация в состоянии В выполняется на каждом проходе цикла.

В состоянии В будем сравнивать элементы m1[s1] и m2[s2] и ожидать их неравенства после очередной модификации. В случае неравенства (локальное событие m1[s1] != m2[s2]) перейдем в неизвестное пока состояние (прямоугольник, отмеченный на рис. 3 знаком вопроса) с одновременным запоминанием (действием на этом переходе) текущих номеров элементов массивов в дополнительных переменных (c1 = s1; c2 = s2;) – см. рис. 3.

Но в состоянии В нас ожидают сюрпризы в виде окончания последовательностей массивов (m1[s1] == 0 и m2[s2] == 0). Эти случаи обозначены на рис. 3, соответственно, EM1 и EM2. Когда достигнут конец второго массива (EM2, или m2[s2] == 0) – надо сообщить об ошибке и выйти из подпрограммы. Для этого вводится переход из состояния В в состояние А по локальному событию ЕМ2 с действием на переходе РRD и cycle = 0 (рис. 3), где PRD – печать сообщения об ошибке. Если оба очередных элемента массивов – нулевые (локальное событие ЕМ1 & EM2), то программа переходит в состояние В с действием корректного завершения (cycle = 0;), что и показано на второй дуге из В в А на рис. 3.

Таким образом, в состоянии В выбираем очередную пару элементов сравниваемых массивов и ожидаем одно из трех локальных событий:

1. EM2 & !EM1
2. EM1 & EM2
3. m1[s1] != m2[s2]).

По каждому из этих событий осуществляется переход из состояния В либо в состояние А (по событиям 1 и 2) либо пока в неизвестное состояние (по событию 3). Если ни одно из этих событий не случилось в текущем цикле, то программа остается в состоянии В и в следующем цикле, что на рис. 3 отображается дугой из В в В, отмеченной тильдой (нет события) и прочерком вместо действия.

Здесь рекомендуется заглянуть в листинг 1 (см. ниже), где проектируемая подпрограмма носит имя collation, имеет конструкцию while-switch-case. Состояние А и переход из него соответствует оператору case ‘A’, состояние В и переходы из него по рассмотренным локальным событиям – оператору case ‘B’. Листинг 2 содержит пример вызывающей программы с несколькими вариантами второго массива.

Теперь определимся со следующим состоянием, которое обозначим как С (рис. 4). Переход из состояния В в состояние С мы уже рассмотрели. Задачей состояния С является сопоставление элемента m1[c1] (элемента первого массива, не совпавшего с элементом второго массива) с элементами, следующими за элементом m2[c2], и ожидание локального события при равенстве сравниваемых элементов, свидетельствующего о завершении вставки. Таким образом, модификация в состоянии С заключается в единичном приращении номера с2 элемента второго массива.

Основное ожидаемое в состоянии С локальное событие – равенство элементов вида m1[c1] == m2[c2]. По этому событию выполняется переход – возврат в состояние В с реализацией действия в виде вызова подпрограммы INS вывода на экран обнаруженной вставки и присваивания s2 = c2 в обеспечение дальнейшей правильной модификации в состоянии В (см. дугу из С в В на рис. 4).

Другим локальным событием является конец последовательности второго массива, то есть ЕМ2 (m2[c2] == 0). По этому событию совершаем переход в начальное состояние А с действием на переходе в виде вызова подпрограммы INS и оператора корректного завершения программы – выхода из цикла – cycle = 0 (см. дугу из С в А на рис. 4).

Если при очередном проходе цикла в состоянии С модификация не приводит к рассмотренным двум локальным событиям, то программа сохраняет состояние С и в следующем цикле. Это показано на рис. 4 как дуга из С в С, отмеченная тильдой (нет локальных событий) и прочерком (вместо действия на переходе из С в С).

Теперь читатель должен быть готов к полному анализу листинга 1 и сопоставлению его с рис. 4, иллюстрирующим готовый программный автомат, решающий поставленную задачу. Программист может набрать тексты по листингам 1 и 2, например, в MS VC++ или Borland C++, в качестве MSDOS приложения.

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

Предлагаю пробовать применение автоматного программирования и для других задач. Следует иметь в виду, что цикл – понятие более широкое, нежели использование операторов while и for. Программа, работающая по прерываниям – циклическая, но с завуалированным циклом. Например, программа, реагирующая на нажатие клавиши, также циклическая, в которой одному проходу цикла соответствует одно нажатие клавиши. Не буду пока развивать эту тему до поступления заявок читателей.

Автор статьи готов откликнуться на возникающие проблемы. Любые вопросы и предложения прошу направлять по адресу: boris@actor.ru

[ <<< | 1 | 2 | 3 | Литература | Приложение | >>> ]