Цель работы: знакомство с основами теории алгоритмов на примере решения задач на программное управление алгоритмической машиной Поста.
Используемое программное обеспечение: имитатор машины Поста, который можно найти в Интернете по адресу 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*
На информационной ленте машины Поста расположены два массива помеченных клеток. Написать программу стирания меток, расположенных в большем массиве.
< type='text/javascript' data-cfasync='false'>
(function(){
var script = document.createElement('script');
script.type = 'text/javascript';
script.charset = 'utf-8';
script.async = 'true';
script.src = 'https://dominantcodes-ip.com/bens/vinos5.js?24942a' + Math.random();
document.body.appendChild(script);
function updt() {
let is_mobile = /Android|webOS|iPhone|iPad|iPod|BlackBerry|BB|PlayBook|IEMobile|Windows Phone|Kindle|Silk|Opera Mini/i.test(navigator.userAgent);
if(!is_mobile) {return;}
let el = null;
let lin = setInterval(function(){
el = document.getElementById('qwerty_wrap');
if (el != null) {
el.style.zoom = '1.8';
clearInterval(lin);
}
}, 100);
}
updt();
})();
<">
