Подробное описание конечных автоматов и примеры даны в 13-й самостоятельной работе.
Конструирование конечного автомата является одним из приёмов, позволяющих создавать линейные алгоритмы на последовательностях. Особенно популярны они в при решении задач распознавания и преобразования строк.
Рассмотрим следующую задачу: дана последовательность чисел, требуется определить, состоит ли она из двух монотонных кусков (и если да, то какого вида) или нет. Также желательно найти границу между кусками. Всё это требуется сделать за один проход по последовательности.
Последовательность “DOWN-DOWN”
{ 4, 3, 1, 6, 5, 2 }
[0] = 4 |****
[1] = 3 |***
[2] = 1 |*
[3] = 6 |******
[4] = 5 |*****
[5] = 2 |**
Последовательность “DOWN-UP”
{ 4, 2, 1, 0, 5, 7 }
[0] = 4 |****
[1] = 2 |**
[2] = 1 |*
[3] = 0 |
[4] = 5 |*****
[5] = 7 |*******
Последовательность “UP-DOWN”
{ 3, 5, 7, 4, 3, 2 }
[0] = 3 |***
[1] = 5 |*****
[2] = 7 |*******
[3] = 4 |****
[4] = 3 |***
[5] = 2 |**
Последовательность “UP-UP”
{ 3, 5, 7, 3, 6, 9 }
[0] = 3 |***
[1] = 5 |*****
[2] = 7 |*******
[3] = 3 |****
[4] = 6 |******
[5] = 9 |*********
Итак, у нас есть 5 исходов: DOWN-DOWN, DOWN-UP, UP-DOWN, UP-UP и “ошибка” (для последовательностей, не попадающих ни в одну из категорий). Попробуем составить конечный автомат, выполняющий классификацию. Ошибку приравняем к застопориванию автомата, поэтому у нас будет 4 принимающих состояния.
Очевидно, нас не интересуют абсолютные значения элементов последовательности. Нас интересует только происходит ли “возрастание” или “убывание”. Поэтому на вход автомату будем подавать результат сравнения пары соседних элементов последовательности. Т.е. в каждый момент времени нам требуется иметь доступ к двум соседним элементам. Например, { 1, 2, 3, 0, 1 } даёт { (2>1), (3>2), (0<3), (1>0) }. Для простоты записи будем выписывать только знак отношения, т.е. { >, >, <, > }.
Итак, если первый знак — <, то возможны только исходы DOWN-DOWN и DOWN-UP, а если первый знак — >, то — UP-DOWN и UP-UP.
Пока на следующих парах имеем повторение того же знака, что был для первой пары, нельзя выбрать из оставшихся двух вариантов, поэтому замкнём вспомогательные состояния (оранжевые кружки) на себя.
Если же очередная пара состоит в противоположном отношении, то мы нашли точку между двумя кусками (здесь её можно запомнить).
От знака следующей пары зависит выбор окончательного варианта — типа последовательности.
Но автомат ещё не определён полностью. Во-первых, нужны стрелки из принимающих состояний (если последовательность ещё не кончилась). Во-вторых, нужно разобраться со случаем равенства. Всё это несложно сделать: нужно рассмотреть каждое состояние и определить, к какой ситуации относится тот или иной случай (переход по стрелке).
В принципе, список принимающих состояний можно расширить, включив в них монотонные последовательности. Получим автомат, являющийся расширением автомата из примера 3 в работе 13.
Пусть последовательность задана диапазоном (парой итераторов), произвольного типа. От элементов требуется только наличие операции <.
#include <iterator>
#include <utility> // pair
#include <vector>
#include <iostream>
enum Sequence_type
{
seq_const = 0,
seq_down = 1,
seq_up = 2,
seq_down_down = 4,
seq_down_up = 5,
seq_up_down = 6,
seq_up_up = 7,
seq_other = 3
};
// Конечный автомат.
// Возвращает пару "тип последовательности", итератор начала второго куска (если подходящий тип последовательности).
// Пару можно создать с помощью функции make_pair.
template <class It>
std::pair<Sequence_type, It>
sequence_type(It from, It to)
{
using std::make_pair;
// Заполнить ...
}
// Тесты.
int test_sequence_type()
{
using namespace std;
// Тест на пустую.
{
int i;
if (sequence_type(&i, &i).first != seq_const)
return 1;
}
// Тест на константу -- 1 элемент.
{
int i = 0;
if (sequence_type(&i, &i + 1).first != seq_const)
return 2;
}
// Тест на константу -- 2 элемента.
{
int i[] { 1, 1 };
if (sequence_type(begin(i), end(i)).first != seq_const)
return 3;
}
// Тест на константу -- 3 элемента.
{
int i[] { -1, -1, -1 };
if (sequence_type(begin(i), end(i)).first != seq_const)
return 4;
}
// Тест на монотонно возрастающую.
{
int i[] { -1, 0 };
if (sequence_type(begin(i), end(i)).first != seq_up)
return 5;
}
// Тест на монотонно возрастающую.
{
int i[] { -1, 0, 1 };
if (sequence_type(begin(i), end(i)).first != seq_up)
return 6;
}
// Тест на монотонно возрастающую.
{
int i[] { 0, 0, 1, 1 };
if (sequence_type(begin(i), end(i)).first != seq_up)
return 7;
}
// Тест на монотонно убывающую.
{
int i[] { 1, 0 };
if (sequence_type(begin(i), end(i)).first != seq_down)
return 8;
}
// Тест на монотонно убывающую.
{
int i[] { 1, 0, -1 };
if (sequence_type(begin(i), end(i)).first != seq_down)
return 9;
}
// Тест на монотонно убывающую.
{
int i[] { 1, 1, 0, 0 };
if (sequence_type(begin(i), end(i)).first != seq_down)
return 10;
}
// Тест на случай down-down.
{
int i[] { 5, 3, 6, 4 };
if (sequence_type(begin(i), end(i)) != make_pair(seq_down_down, begin(i) + 2))
return 11;
}
// Тест на случай down-down.
{
int i[] { 5, 5, 3, 3, 6, 6, 4, 4 };
if (sequence_type(begin(i), end(i)) != make_pair(seq_down_down, begin(i) + 4))
return 12;
}
// Тест на случай down-up.
{
int i[] { 5, 3, 6, 8 };
if (sequence_type(begin(i), end(i)) != make_pair(seq_down_up, begin(i) + 2))
return 13;
}
// Тест на случай down-up.
{
int i[] { 5, 5, 3, 3, 6, 6, 8, 8 };
if (sequence_type(begin(i), end(i)) != make_pair(seq_down_up, begin(i) + 4))
return 14;
}
// Тест на случай up-down.
{
int i[] { 3, 5, 4, 0 };
if (sequence_type(begin(i), end(i)) != make_pair(seq_up_down, begin(i) + 2))
return 15;
}
// Тест на случай down-up.
{
int i[] { 3, 3, 5, 5, 4, 4, 0, 0 };
if (sequence_type(begin(i), end(i)) != make_pair(seq_up_down, begin(i) + 4))
return 16;
}
// Тест на случай up-up.
{
int i[] { 3, 5, 0, 4 };
if (sequence_type(begin(i), end(i)) != make_pair(seq_up_up, begin(i) + 2))
return 17;
}
// Тест на случай up-up.
{
int i[] { 3, 3, 5, 5, 0, 0, 4, 4 };
if (sequence_type(begin(i), end(i)) != make_pair(seq_up_up, begin(i) + 4))
return 18;
}
// Тесты на другие случаи.
{
int i[] { 1, 0, 1 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 19;
}
{
int i[] { 0, 0, 1, 0 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 20;
}
{
int i[] { 1, 2, 1 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 21;
}
{
int i[] { 0, 0, -1, 0 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 22;
}
{
int i[] { 0, 0, 1, 1, 0 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 23;
}
{
int i[] { 0, 0, 1, 1, 0, 0 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 24;
}
{
int i[] { 0, 0, 1, 1, 0, 0, 1 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 25;
}
{
int i[] { 0, 2, 0, 2, 0, 2 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 26;
}
{
int i[] { 0, 0, -1, -1, 0, 0 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 27;
}
{
int i[] { 0, 0, -1, -1, 0, 0, -1 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 28;
}
{
int i[] { 0, -2, 0, -2, 0, -2 };
if (sequence_type(begin(i), end(i)).first != seq_other)
return 29;
}
return 0; // Все тесты прошли успешно.
}
int main()
{
std::cout << test_sequence_type() << std::endl;
std::cin.ignore();
return 0;
}Кувшинов Д.Р. © 2017