Практическая работа № 2.2 "Автоматическая обработка данных"

   Цель работы: знакомство с основами теории алгоритмов на примере решения задач на программное управление алгоритмической машиной Поста.
   Используемое программное обеспечение: имитатор машины Поста можно найти в Интернете по этой ссылке.
   Система команд машины Поста: (везде буква n обозначает номер текущей команды):

   Задание 1

   Составить программу перевода информационной ленты машины Поста из начального состояния (н.с.) в конечное (к.с.):

   Задание 2

   1. Выполните на машине Поста программу:

       1 v 2                                    4 ← 5
       2 → 3                                   5 v 6
       3 ? 2, 4                                 6!

   2. Какую задачу решает исполнитель по этой программе?
   3. Что произойдёт, если начальное состояние информационной ленты будет иметь следующий вид?

   В следующих задачах считается, что n расположенных подряд меток обозначают число n (непозиционная система счисления с основанием 1).

   Задание 3

   Написать для машины Поста программу сложения двух чисел, записанных на ленте и расположенных через одну пустую клетку друг от друга. Начальное положение каретки - под пустой клеткой, отделяющей числа.

   Задание 4

   Написать для машины Поста программу вычитания двух чисел, разделенных одной пустой клеткой. Уменьшаемое не меньше вычитаемого. Начальное положение каретки - под пустой клеткой, отделяющей уменьшаемое от вычитаемого.
   Указание. Стирать метки по одной у каждого числа, пока у вычитаемого не кончатся все метки.

   Задание 5

   Используя программу вычитания, проверить:
   а) что получится, если уменьшаемое равно вычитаемому;
   б) что получится, если уменьшаемое меньше вычитаемого;

   Задание 6

   Написать для машины Поста программу деления числа, записанного метками, на 2. Исходное число должно делиться на 2 без остатка.
   Указание. Стереть каждую вторую метку; уплотнить оставшиеся метки.

   Задание 7

   Используя программу деления числа на 2:
   а) проверить, что получится для числа 2;
   б) модифицировать программу с учетом числа 2.
   Указание. Справа от пустой клетки поставить метку, а слева стереть две метки. Так поступать до тех пор, пока слева остаются метки.

   Задание 8

   На информационной ленте машины Поста на расстоянии в n клеток друг от друга расположены две помеченные метками клетки. Начальное положение каретки - под левой из помеченных клеток. Какую работу выполнит машина Поста по программе?

       1 → 2                                   3 ← 4
       2 ? 1, 3                                 4 ? 3, 1

   Задание 9

   Написать для машины Поста программу умножения на 2 числа, записанного метками на ленте.
   Указание. Через одну пустую клетку поставить две метки, а в исходном числе стереть одну. Так поступать, пока в исходном числе остаются метки.

   Задание 10*
   
   Написать для машины Поста программу, проверяющую, делится ли записанное метками число на 5.

   Задание 11*
   
   На информационной ленте машины Поста помечена 2n - 1 клетка. Составить программу отыскания средней помеченной клетки и стирания метки в ней.

   Задание 12*
   
   На информационной ленте машины Поста расположены два массива помеченных клеток. Написать программу стирания меток, расположенных в большом массиве.