Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
kvi232
Сообщений: n/a
#1

Модель машины Поста - C++

21.11.2010, 16:37. Просмотров 964. Ответов 0
Метки нет (Все метки)

МП – машина Поста
Абстрактная МП представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой. Вдоль ленты может перемещаться головка.
Команды МП состоят из 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.11.2010, 16:37     Модель машины Поста
Посмотрите здесь:

C++ считать код машины Тьюринга
C++ Эмулятор трёхадресной машины.
Реализовать игру человека и машины по заполнению “Греко-латинского квадрата” C++
Исходники виртуальной машины C++
C++ Идея собирать узлы в кластеры во время простоя машины
C++ Машина Поста (да пофиг)
Добавить два числа с помощью Машины Тьюринга. C++
Программа на C++, которая переводит цветовую модель RGB в модель HSV C++
C++ Проверить делится ли число нацело с помощью машины тьюринга
C++ Как код с++ скопировать с виртуальной машины (ubuntu) на основную (windows)?
C++ Написание виртуальной машины
C++ Определение типа номера машины

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 22:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru