Алгоритм поведения и автоматная модель стрелка
На первый окрик: "Кто идет?" - он стал шутить,
На выстрел в воздух закричал: "Кончай дурить!"
Я чуть замешкался и, не вступая в спор,
Чинарик выплюнул - и выстрелил в упор.
В. Высоцкий
В задаче Майхилла необходимо определить, как нужно действовать стрелкам, построенным в шеренгу, чтобы одновременно открыть стрельбу, если команда "Огонь!" (или "Пли!") подается крайнему в шеренге, а обмен информацией разрешается только между соседями.
Из известных решений данной задачи своей простотой и, главное, "автоматным" подходом привлекает приведенное в работе [2]. Оно заключается в том, что каждый стрелок должен руководствоваться следующим набором указаний.
1. Если ты левофланговый и получил приказ "Шеренга, пли!", то запомни число 1 - свой порядковый номер - и ровно через секунду сообщи его соседу справа.
2. Если ты неправофланговый и сосед слева сообщил тебе число V, запомни число V+1 - свой порядковый номер - и ровно через секунду сообщи его соседу справа.
3. Если ты правофланговый и сосед слева сообщил тебе число n-1, то ровно через секунду ответь ему: "Готов!" и приступай к обратному счету в уме: n, n-1, n-2, ..., отсчитывая по одному числу в секунду.
4. Если ты не правофланговый и сосед справа доложил тебе: "Готов!", то ровно через секунду приступай к обратному счету в уме: V, V-1, V-2, ..., где V - твой порядковый номер, отсчитывая по одному числу в секунду. При этом, если V>1, т.е. если ты не левофланговый, то ровно через секунду после получения сообщения от соседа справа доложи: "Готов!" соседу слева.
5. Досчитав до нуля, стреляй!
Автоматная модель поведения стрелка
Аналогичные указания даются, когда приказ получен правофланговым.
Несложно показать, что решение не зависит от выбранного временного интервала. Более того, этот интервал может быть и "плавающим" - лишь бы он был одинаковым для всех стрелков на каждом шаге счета. Благодаря данному свойству алгоритм легко реализовать в рамках сетевой автоматной модели.
На рисунке показан КА, моделирующий поведение стрелка. Стрeлки соответствуют синхронизирующей информации, которая поступает к стрелку от его соседей слева и справа. Предикаты и действия автомата можно условно описать следующим образом:
// Предикаты
x1 Состояние соседа слева "Огонь!"?
// Команда "Огонь";
x2 Состояние соседа справа "Готов!"?
x3 Свой номер не равен нулю?
// Действия
y1 Установить свой номер: взять номер
соседа слева
и увеличить на 1
y2 Уменьшить свой номер на 1
y3 Произвести выстрел
Кстати, эти строки в дальнейшем можно превратить в комментарии к операторам "автоматной программы".
