Задачи для решения.
1.Для каждой пары алгоритмов Н1 и Н2 построить их композицию относительно алфавита {a,b} в виде нормального алгоритма Н (Н=Н2(Н1)):
2.Заданы следующие три НАМ:
Является ли алгоритм Н композицией алгоритмов Н1 и Н2 (Н=Н2(Н1))относительно алфавита {a,b,c}? Ответ обосновать.
3. Заданы следующие пять НАМ:
Определить, есть ли среди этих алгоритмов такие, которые являються композицией других, если да, то указать все такие композиции.
Глава 4. Машина Поста.
Программы для решения всех задач этой главы могут быть интерпретированы как выполнение элементарных арифметических операций. Важно показать, как с помощью простейших операций, которыми располагает машина Поста, можно выполнять арифметические операции — основу любого современного процессора.
Практическая работа №13. Работа с массивами
Пример 1. Работа с массивами
На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.
Решение.
1. ? 2; 3 (команды 1 и 2 — передвигаем каретку к массиву)
2. –> 1
3. –> 4 (команды 3 и 4 — передвигаем каретку к концу массива)
4. ? 5; 3
5. V 6 (команды 5–7 — ставим 2 метки в конце массива)
6. –> 7
7. V 8
8. !
Пример 2. Даны два массива меток, которые находятся на не- котором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.
Решение.
Пример 3. На ленте задана последовательность массивов, включающая в себя один и более массивов. При этом два соседних массива отделены друг от друга одной пустой ячейкой. Необходимо на ленте оставить один массив длиной равной сумме длин массивов, присутствовавших изначально. Каретка находится над крайней левой меткой первого (левого) массива.
Решение.
Пример 4. На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.
Решение. Запишем решение алгоритма в словесной форме.
1. Ищем правый край массива m, двигаясь слева направо.
2. Стираем правую метку массива m.
3. Ищем правый край массива n, двигаясь слева направо.
4. Стираем левую метку массива n.
5. Проверяем, мы стерли последнюю метку в массиве n (в этом случае следующая справа ячейка должна быть пустой)?
6. Если стерли последнюю метку, то конец алгоритма.
7. Иначе ищем правый конец массива m, двигаясь справа налево.
8. Переход на шаг 2.
1. –> 2 (команды 1–3: ищем левую метку массива m)
2. ? 3; 1
3. <– 4
4. X 5 (стираем левую метку массива m)
5. ? 6; 7
6. –> 5
7. X 8 (стираем левую метку массива n)
8. –> 9
9. ? 12; 10 (стерли последнюю метку в массиве n?)
10. <– 11 (ищем левый край массива m)
11. ? 10; 4
12. !
Пример 5. На ленте заданы два массива. Найти модуль разности длин массивов. Каретка располагается над первой ячейкой левого массива.
Решение.
1. –> 2
2. ? 3; 1 (идем до конца первого массива)
3. <– 4
4. X 5 (удаляем крайний правый элемент 1-го массива)
5. <– 6
6. ? 14; 7 (проверяем, что в 1-м массиве еще остались метки)
7. –> 8
8. ? 7; 9
9. X 10 (удаляем первую метку 2-го массива)
10. –> 11
11. ? 17; 12 (проверяем, что во 2-м массиве еще остались метки, иначе — завершение)
12. <– 13
13. ? 12; 4
14. –> 15 (мы удалили полностью 1-й массив)
15. ? 14; 16
16. X 17
17. !
Пример 6. На ленте задан массив. Удвоить массив в два раза. Каретка располагается над первой ячейкой массива.
Решение. В результате работы программы справа от исходного массива будет сформирован новый массив удвоенной длины, исходный массив будет стерт.
Пример 7. На ленте задан массив. Вычислить остаток от деления длины заданного массива на 3. Каретка располагается над первой ячейкой массива.
Решение.
Пример 8. На ленте машины Поста расположен массив из n меток. Составить программу, действуя по которой машина выяснит, делится ли число n на 3. Если да, то после массива через одну пустую ячейку поставить метку.
Решение. Нужно проверить, что массив состоит не менее чем из трех меток, сместиться правее них и снова решать ту же задачу. Если правее очередных трех меток окажется пробел, то за ним поставить еще одну метку.
