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

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

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

boris@actor.ru

Федеральный научно-производственный центр ГУП "НПО "Аврора""

Опубликована в журнале BYTE/Россия, 2000, №11

Статья предназначается программистам, работающим в среде C/C++, желающим ознакомиться с автоматным программированием, которое предполагает использование аппарата конечных автоматов. Данный подход требует определенных психологических усилий. Однако после его освоения возникает вопрос: как я мог программировать иначе? Автоматное программирование позволяет решать практически любые сложные циклические задачи с минимальными затратами на отладку. Приводятся абстрактный и конкретный примеры с листингом на языке программирования C, доступные, в том числе, начинающим программистам.

Наиболее важными вехами последних 15–20 лет в создании программ на языках высокого уровня являются методологии структурного [1] и объектно-ориентированного программирования [6]. Параллельно с ними сравнительно давно используется метод “автоматного” программирования. Этот метод назван так потому, что в основу проектирования программы закладывается алгоритм - конечный автомат в виде диаграммы состояний, или таблицы последовательных переходов и выходов [2].

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

Тем временем, на Западе эта методология активно развивалась, в первую очередь Харелом (например, [5]). Диаграммы состояний (как основа автоматного подхода к реализации различных задач, решаемых программным путем), вошли неотъемлемой частью в основные принципы объектно-ориентированного программирования [6]. Кроме того, такие диаграммы входят и в стандарт UML [7]. Но по этим книгам даже опытному программисту трудно перешагнуть некий психологический барьер для перехода на автоматное программирование.

Предпосылки написания статьи.

Теорию автоматов преподают не везде. В технических ВУЗах преподают эту теорию применительно к синтезу цифровой аппаратуры, но не применительно к программированию (Такие выводы сделаны моим коллегой Шалыто А.А. для ведущих Питерских ВУЗов). По специальностям, связанным с программированием, теория автоматов преподается либо абстрактно, либо применительно к задачам распознавания языковых конструкций, и только на основе табличной интерпретации. В итоге, выпускник современного ВУЗа не способен использовать конечные автоматы для широкого круга задач. Когда-то я работал руководителем очень большой группы программистов и пытался внедрить "в массы" использование автоматов в программах различного назначения. Ничего не вышло. Только один - двое могли усвоить лишь некоторые мои программы, но самостоятельно решать подобные задачи не могли. Лишь теперь набран необходимый материал для широкого распространения метода автоматного программирования в задачах циклической природы различного назначения.

Табличная программная интерпретация конечного автомата использовалась мною с 1975 по 1992 годы. То есть до тех пор, пока не появилась книга [12], где вместо таблицы предложено использовать оператор switch-case (Примерно в то же время, этот оператор предложил использовать наш сотрудник Кондратьев, что привело впоследствии к выходу в свет книги [9], посвященной задачам логического управления).

Основной недостаток использования таблицы состоит в том, что абсолютно все буквы входного алфавита необходимо вычислять до входа в таблицу, или до вычисления нового состояния и выхода по таблице. Хорошо, если буквам входного алфавита соответствуют сигналы от клавиатуры или синтаксические единицы распознаваемого текста. В противном случае следует вычислять для каждой упомянутой буквы соответствующее логическое выражение, да к тому же, предварять такое вычисление некоторыми действиями по модификации аргументов этих выражений. Это не всегда возможно совместить без порчи указанных аргументов. Помимо этого, для реализации действия на переходе требуется переключатель switch(идентификатор_действия). И такая программа начисто теряет смысл и наглядность. Поэтому она никому кроме автора не понятна.

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

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

Автору этой статьи повезло: в ВУЗе нам читали лекции по теории автоматов, в том числе методику перехода от блок-схем (граф-схем) алгоритмов к графу переходов конечного автомата. С тех пор я твердо усвоил: практически любой алгоритм, включающий цикл (циклы) реализуется конечным автоматом. Почти во всех своих программах мне было очень удобно использовать конечные автоматы, причем такие программы почти никогда не требовали отладки. В [8] автором предложены автоматы со скрытыми переходами, расширяющие область применения конечных автоматов в программировании. Далее до 1998 г. автор не публиковал свои результаты в области автоматного программирования, ошибочно полагая, что этот вопрос в программировании давно решен.

Однако, как показала публикация [9] моего коллеги, даже в такой, казалось бы заезженной области, программной реализации алгоритмов логического управления, использование автоматного подхода является в нашей державе нонсенсом. Что уж говорить об автоматной реализации обычных циклических программ!

Общие понятия

Перейдем непосредственно к рассмотрению автоматного программирования на основе конструкции while-switch-case. При этом, вместо принятой терминологии, предлагается более понятная массовому читателю – программисту.

В работе [10, с. 168-177] рассматривается задача преобразования циклического алгоритма, представленного традиционной блок-схемой с условными и операторными вершинами, в диаграмму состояний или граф переходов конечного автомата (см. приложение). Задача решается для произвольного циклического алгоритма. Это основной психологический момент рассматриваемого вопроса, а именно: произвольный циклический алгоритм можно задать в виде графа переходов конечного автомата. Обратная задача – преобразование графа переходов в традиционную блок-схему рассматривается в [4, c. 39–42].

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

В отличие от традиционных алгоритмов, включающих два вида компонент: условие и действие, конечный автомат включает дополнительно состояния. Не будем описывать известные положения теории автоматов, с которыми можно ознакомиться, например в [11, 9, 10]. Вместо этого станем рассматривать практические аспекты создания автоматных алгоритмов и программ, в том числе на простом примере.

Вначале представим в общем виде автоматный алгоритм, пример которого изображен на рис. 1.

Прежде всего, обратим внимание на рамку, имитирующую цикловую природу реализации автомата. В частности, вверху явно указан оператор “while(cycle)”, где “cycle” – признак продолжения цикла, который перед передачей управления оператору while должен быть установлен в ненулевое значение. Итак, автомат реализуется программной конструкцией на Си:

static char state = ‘A’;
int cycle = 1;
while (cycle) 
{
  тело_автомата ;
}

где state и тело_автомата подлежат дальнейшему рассмотрению.

Для понимания автоматной программы следует ввести определения: состояние, локальное событие, переход, модификация, действие на переходе. Наиболее сложным для восприятия конечных автоматов является понятие “состояние”. Однако начнем с определения “локальное событие”.

Локальным событием в автоматной программе будем считать положительный результат (не нулевое значение) вычисления некоторого логического выражения. Если логических выражений в программе более одного, то каждому из них ставится в соответствие свое локальное событие. Логическим выражением считается произвольная одноименная конструкция языка программирования C, в том числе: булева формула, выражение с операторами сравнения (аргументами которых могут быть и целочисленные функции). Локальное событие будем обозначать символом Х_ij и отождествлять с буквой входного алфавита конечного автомата.

В общем случае, состояние чего – либо, например, воды (жидкость, твердое – лед, газообразное – пар), не требует пояснений. Отметим, что та же вода в жидком состоянии “ожидает” наступления “события” (повышения температуры выше 100 град. или понижения температуры ниже 0 град.) для перехода в другое состояние. Если ни одно из этих двух событий не произошло, то вода остается в прежнем своем (жидком) состоянии.

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

Другими словами: состояние автоматной программы – это зацикливание на одном и том же фрагменте программы до наступления локального события.

Автоматная программа имеет несколько состояний, для обозначения которых отводится специальная символьная переменная – “state”. Обязательно наличие начального состояния, обозначаемого, например, символом ‘A’.

Переход в автоматной программе есть переход от текущего состояния, например, ‘B’, в новое состояние, например, ‘C’, при наступлении локального события X_BC, приписанного к состоянию ‘B’. При этом переменная состояния state = ‘B’ изменяется на state = ‘C’.

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

Автоматная программа в каждом проходе цикла “while(cycle)” должна изменять значения аргументов вычисляемых логических выражений. В обеспечение этого каждое состояние должно иметь операторы модификации указанных аргументов.

Теперь рассмотрим абстрактный пример автоматной программы. Внутри прямоугольника – цикла на рис. 1 показан граф переходов (диаграмма состояний) некоторого автомата. Прямоугольниками, обозначенными буквами A – D, указаны вершины графа, обозначающие его четыре (в данном примере) состояния.

Укажем, что перед вычислением логических выражений, определяющих локальные события, во фрагменте-состоянии, как правило, осуществляется однократная модификация одной или нескольких переменных, обеспечивающих продвижение по циклу. Например, если автомат реализует анализ массива (файла), то модификация означает переход к очередному элементу массива (к очередной записи файла). В начальном состоянии модификация не производится. Модификация на рис. 1 обозначена символом Z с индексом соответствующего состояния.

Состояния реализуются оператором switch(state) – case [12, 9]. Например, программа для автомата (рис. 1) имеет следующую конструкцию:

static char state = ‘A’;
int cycle = 1;
while(cycle)
{
  switch(state)
  {
  case ‘A’: 
    состояние A пока_не_рассматриваем;
    break;
  case ‘B’:
    состояние B пока_не_рассматриваем;
    break;
  case ‘C’:
    состояние C пока_не_рассматриваем;
    break;
  case ‘D’: 
    состояние D пока_не_рассматриваем;
    break;
  }
}

Переходы между состояниями обозначены на рис. 1 стрелками. Переходы помечены дробью: локальное событие Х / действие на переходе Y. За обозначением локального события сокрыто соответствующее логическое выражение.

Отметим обязательное правило: анализируемые логические выражения (условия), прописанные в одном и том же состоянии, должны быть обязательно ортогональны, что означает невозможность появления одновременно двух и более локальных событий. Локальные события, или логические условия, на рис. 1 обозначены символом Х с двумя индексами, первый из которых обозначает текущее состояние, а второй – состояние, в которое должна перейти программа в следующем цикле при наступлении данного локального события.

Локальному событию взаимно однозначно соответствует переход из текущего состояния в другое состояние. Если ни одно из вычисляемых в данном состоянии локальное событие не наступило, то сохраняется текущее состояние, и этому соответствует логическое условие, отрицающее любое из локальных событий – условий переходов в другие состояния (смотри “петли” - дуги, исходящие и заходящие в одну и ту же вершину - у вершин B, C, D на рис. 1).

Итак, по локальному событию программа переходит в следующем цикле в новое или остается в старом состоянии. Однако, прежде, чем перейти в новое состояние, программа должна совершить некоторое действие на переходе, следующее за соответствующим локальным событием и предваряющее модификацию в соответствующем переходу новому (прежнему) состоянию (в следующем цикле). Таким действием может быть произвольный оператор языка С++, включая произвольную последовательность произвольных операторов (в том числе вызов подпрограмм, в частности реализующих и другие автоматы, но - это отдельная тема). На рис.1 такие действия стоят после дробной наклонной черты и обозначаются символом Y с индексами обозначающими направление перехода.

Отдельно, через запятую, указаны операторы вида “cycle = 0”, что означает конец циклической обработки. При этом направление перехода всегда к начальной вершине, она же является и заключительной для обеспечения корректного повторного использования данной подпрограммы – автомата.

Отметим, что правильная программа – автомат должна содержать переходы из любой вершины в начальную с указанным оператором обнуления переменной cycle во избежание зацикливания в одном состоянии. (В рассмотренном примере в состоянии С возможно зацикливание).

При первом обращении к автоматной подпрограмме, она находится в начальном состоянии, в котором не ожидается ни одно локальное событие. При этом осуществляется безусловный переход в состояние ‘B’ и выполняется действие Y_AB на этом переходе.

После данных пояснений приведем частично программу, реализующую автомат (рис. 1):

static char state = ‘A’;
int cycle = 1;
while(cycle)
{
  switch(state)
  {
  case ‘A’: 
    оператор YAB;
    state = ‘B’;
    break;

  case ‘B’:
    оператор ZB;
    if(XBA)
    {
      оператор YBA;
      cycle = 0;
      state = ‘A’;
    }
    else if(XBC)
    {
      оператор YBC;
      state = ‘C’;
    }
    else // if ( ! ( XBA || XBC ) == 1 ) 
    {
      оператор YBB;
      // state = ‘B’;
    }
    break;

  case ‘C’: 
    состояние C не_рассматриваем;
    break;

  case ‘D’: 
    состояние D не_рассматриваем;
    break;

  }
}

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

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

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

М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. Шнейдерман Б. Психология программирования. М.: Радио и связь. 1984.
2. Байцер Б. Архитектура вычислительных комплексов. Том 1. М.: Мир. – 1974.
3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х томах. М.: Мир. – 1978.
4. Срибнер Л.А. Программируемые устройства автоматики. К.: Технiка. 1982.
5. Harel D. Statecharts: A Visual Formalism for Complex Systems. Science of Computer Programming. 1987. Vol. 8, P. 231 – 274.
6. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.: “Изд-во Бином”, СПб: “Невский диалект”. – 1998.
7. Буч Г., Рамбо Д., Джекобсон А. Язык UML. Руководство пользователя. М.: ДМК. – 2000.
8. Кузнецов Б.П. Стандартная реализация управляющих программ // Судостроительная промышленность. Сер. Системы автоматизированного проектирования – 1986. с. 51 – 55.
9. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука. – 1998.
10. Баранов С.И. Синтез микропрограммных автоматов. Л.: Энергия. – 1979.
11. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат. – 1988.
12. Джамп Д. AutoCAD. Программирование. М.: Радио и связь. – 1992.

Приложение. Программа, реализующая рассматриваемый автомат

Листинг 1 Подпрограмма сличения - collation

// collation.cpp Сличение числовых массивов, завершающихся нулем.
// (Пример автоматного программирования)
// Copyright © Кузнецов Б.П. Санкт-Петербург 06.08.2000 
// boris@actor.ru
#include <stdio.h>

void insert(int s2, int c2, int *m2); // вывод на экран вставки

void collation(int *m1, int *m2) // подпрограмма сличения ==========
                                 // m1, m2 - сличаемые масивы
{ 
  static char state = 'A'; // символ состояния подпрограммы сличения
  int cycle = 1; // 0 - признак окончания цикла
  int s1, s2; // текущие номера элементов двух массивов
  int c1, c2; // запоминаемые номера элементов двух массивов

  while(cycle) // локальный цикл подпрограммы
    switch(state) // распознавание текущего состояния графа переходов
    {
    case 'A': // исходное состояние
        s1 = s2 = -1; // подготовка к счету элементов массивов
        state = 'B'; // переход к состоянию В
        break;

    case 'B': // состояние ожидания неравенства элементов массивов
                // (вставки)
        s1++; s2 ++; // переход к очередной паре элементов массивов
        if(!m2[s2] && m1[s1]) // конец второго массива
        {
          printf("\n Массив М1 надо сличать на удаление\n");
          state = 'A'; // перевод подпрограммы в исходное состояние
          cycle = 0; // обеспечение выхода из цикла
        }
        else if(m1[s1] == m2[s2] && !m1[s1]) // конец обоих массивов
        {
          state = 'A'; // перевод подпрограммы в исходное состояние
          cycle = 0; // обеспечение выхода из цикла
        }
        else if(m1[s1] != m2[s2]) // достигли очередной вставки
        { 
          c1 = s1;
          c2 = s2; // запоминаем текущие номера элементов массивов
          state = 'C'; // переход к состоянию С
        }
        else ; // элементы массивов равны и не нулевые
        // продолжаем цикл в состоянии В
        break;

    case 'C': // состояние ожидания равенства элементов после вставки
        c2++; // переход к очередной строке второго массива
        if(!m2[c2]) // конец второго массива - вставка до его конца
        {
          insert(s2, c2 - 1, m2); // печать вставки
          state = 'A'; // перевод подпрограммы в исходное состояние
          cycle = 0; // обеспечение выхода из цикла
        }
        else if(m1[c1] == m2[c2]) // конец вставки
        {
          insert(s2, c2 - 1, m2); // печать вставки
          s1 = c1;
          s2 = c2; // подготовка к продолжению сравнения массивов
          state = 'B'; // возврат к состоянию В
        }
        else ; // пока еще "продолжается" вставка 
               // продолжаем цикл в состоянии С
        break;
    }
} // collation 06.08.2000 =========================================


void insert(int s2, int c2, int *m2) // вывод на экран вставки ====
{
  int i;
  printf("\ninsert: ");
  for(i = s2; i <= c2; i++)
    printf("%d ",m2[i]);
} // insert 06.08.2000 =============================================

Листинг 2 Вызывающая программа main

// main.cpp - пробная программа сличения на вставку 05.08.2000
// Copyright © Кузнецов Б.П. Санкт-Петербург 2000
#include <stdio.h>
#include <conio.h>

void collation(int *m1, int *m2);
main() //=========================================================
{
  static int M1[] = { 1, 2, 3, 4, 5, 6, 7, 0 };
  static int M2[] = { 28, 1, 2, 3, 4, 5, 6, 7, 0 };
  static int M3[] = { 38, 39, 30, 1, 2, 3, 4, 5, 6, 7, 0 };
  static int M4[] = { 1, 2, 3, 4, 5, 6, 7, 48, 0 };
  static int M5[] = { 1, 2, 3, 4, 5, 6, 7, 58, 59, 50, 0 };
  static int M6[] = { 1, 2, 3, 68, 4, 5, 6, 7, 0 };
  static int M7[] = { 1, 2, 3, 78, 79, 70, 4, 5, 6, 7, 0 };
  static int M8[] =
      { 1, 2, 80, 81, 82, 3, 4, 5, 83, 84, 6, 7,  85, 86, 87,0 };

  printf("\n\n collation M1 & M2");
  collation(M1, M2);
  printf("\n\n collation M1 & M3"); 
  collation(M1, M3);
  printf("\n\n collation M1 & M4");
  collation(M1, M4);
  printf("\n\n collation M1 & M5");
  collation(M1, M5);
  printf("\n\n collation M1 & M6");
  collation(M1, M6);
  printf("\n\n collation M1 & M7");
  collation(M1, M7);
  printf("\n\n collation M1 & M8");
  collation(M1, M8);

  getch();

} // main 05.08.2000 =============================================