МП – машина Поста
Абстрактная МП представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой. Вдоль ленты может перемещаться головка.
Команды МП состоят из 3 параметров: n K m (n – номер текущей команды, К – команда, m – номер следующей команды). Обозначим действия латинскими буквами
Существует всего 6 видов команд МП (примеры):
Формат Действие
1 L 2 Команда №1: переместить головку на 1 клетку влево и перейти к команде 2
5 R 37 Команда №5: переместить головку на 1 клетку влево и перейти к команде 37
2 M 3 Команда №2: поставить метку в текущую клетку и перейти к команде 3
11 С 3 Команда №11: стереть метку из текущей клетку и перейти к команде 3
6 3 1 Команда 6: Если в клетке метка отсутствует, перейти к команде 3, иначе – к команде 1
4 S 4 Команда 4: Остановить машину (stop)
Не нужно путать номера ячеек ленты (их просто нет) с номерами команд программы МП
Примеры программ МП приведены в книге.
Входные данные:
Состояние определяется следующим образом:
В первой строке – фрагмент бесконечной ленты, который и содержит информацию. Наличие метки – 1, отсутствие – «.» (точка). Фрагмент может начинаться с любого количества меток (первого числа) или пустот. Пустая лента отображается одной точкой.
В следующей строке «*» отмечено стартовое положение головки.
В следующих строках – программа в командах МП (каждая строка – одна команда).
Выходные данные:
Текстовый файл содержит по 2 строки, отображающие состояние МП после выполнения очередной команды (содержание ленты и положение головки). Если программа МП завершилась корректно, вывести в последней строке «ОК», при аварийном завершении – «CRUSH». Параллельно результаты должны выводиться на экран, чтобы отследить зацикливание некорректной программы.
Пример: На ленте записаны 2 числа через 1 пробел. Головка находится левее 1-го числа. Программа прибавляет 1 ко 2-му числу таким образом, чтобы не перемещать головку до конца 2-го числа.
Входные данные:
...111.1.
*
1 R 2
2 1 3
3 L 4
4 M 5
5 R 6
6 5 7
7 M 8
8 L 9
9 C 10
10 S 10
Выходные данные:
Step 0
...111.1.
*
step 1
...111.1.
*
step 2
...111.1.
*
step 3
...111.1.
*
step 4
..1111.1.
*
step 5
..1111.1.
*
step 6
..1111.1.
*
step 7
..1111.1.
*
step 8
..1111.1.
*
step 9
..111111.
*
step 10
..111111.
*
step 11
..111.11.
*
STOP
Абстрактная МП представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой. Вдоль ленты может перемещаться головка.
Команды МП состоят из 3 параметров: n K m (n – номер текущей команды, К – команда, m – номер следующей команды). Обозначим действия латинскими буквами
Существует всего 6 видов команд МП (примеры):
Формат Действие
1 L 2 Команда №1: переместить головку на 1 клетку влево и перейти к команде 2
5 R 37 Команда №5: переместить головку на 1 клетку влево и перейти к команде 37
2 M 3 Команда №2: поставить метку в текущую клетку и перейти к команде 3
11 С 3 Команда №11: стереть метку из текущей клетку и перейти к команде 3
6 3 1 Команда 6: Если в клетке метка отсутствует, перейти к команде 3, иначе – к команде 1
4 S 4 Команда 4: Остановить машину (stop)
Не нужно путать номера ячеек ленты (их просто нет) с номерами команд программы МП
Примеры программ МП приведены в книге.
Входные данные:
Состояние определяется следующим образом:
В первой строке – фрагмент бесконечной ленты, который и содержит информацию. Наличие метки – 1, отсутствие – «.» (точка). Фрагмент может начинаться с любого количества меток (первого числа) или пустот. Пустая лента отображается одной точкой.
В следующей строке «*» отмечено стартовое положение головки.
В следующих строках – программа в командах МП (каждая строка – одна команда).
Выходные данные:
Текстовый файл содержит по 2 строки, отображающие состояние МП после выполнения очередной команды (содержание ленты и положение головки). Если программа МП завершилась корректно, вывести в последней строке «ОК», при аварийном завершении – «CRUSH». Параллельно результаты должны выводиться на экран, чтобы отследить зацикливание некорректной программы.
Пример: На ленте записаны 2 числа через 1 пробел. Головка находится левее 1-го числа. Программа прибавляет 1 ко 2-му числу таким образом, чтобы не перемещать головку до конца 2-го числа.
Входные данные:
...111.1.
*
1 R 2
2 1 3
3 L 4
4 M 5
5 R 6
6 5 7
7 M 8
8 L 9
9 C 10
10 S 10
Выходные данные:
Step 0
...111.1.
*
step 1
...111.1.
*
step 2
...111.1.
*
step 3
...111.1.
*
step 4
..1111.1.
*
step 5
..1111.1.
*
step 6
..1111.1.
*
step 7
..1111.1.
*
step 8
..1111.1.
*
step 9
..111111.
*
step 10
..111111.
*
step 11
..111.11.
*
STOP