Учебник для 10 класса

ИНФОРМАТИКА

Работа 2.2. Автоматическая обработка данных

Цель работы: знакомство с основами теории алгоритмов на примере решения задач на программное управление алгоритмической машиной Поста.

Используемое программное обеспечение: имитатор машины Поста, который можно найти в Интернете по адресу http://priklinfа.narod.ru/anti800.htm

Система команд машины Поста: (везде буква n обозначает номер текущей команды):

Задание 1

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

Задание 2

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

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

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

Задание 3

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

Задание 4

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

Указание. Стирать метки по одной у каждого числа, пока у вычитаемого не кончатся все метки.

Задание 5

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

а) уменьшаемое равно вычитаемому;

б) уменьшаемое меньше вычитаемого.

Задание 6

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

Указание. Стереть каждую вторую метку; уплотнить оставшиеся метки.

Задание 7

Используя программу деления числа на 2:

а) проверить, что получится для числа 2;

б) модифицировать программу с учетом числа 2.

Указание. Справа от пустой клетки поставить метку, а слева стереть две метки. Так поступать до тех пор, пока слева остаются метки.

Задание 8

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

Задание 9

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

Указание. Через одну пустую клетку поставить две метки, а в исходном числе стереть одну. Так поступать, пока в исходном числе остаются метки.

Задание 10*

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

Задание 11*

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

Задание 12*

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