§ 3.1. Алгоритмы и исполнители

Новая глава посвящена алгоритмам, и начинается она с простого вопроса: как устроена любая инструкция, по которой решают задачу? Заварить чай, собрать модель по схеме, перевести число из десятичной системы в двоичную, дойти от дома до новой школы — каждое из этих дел раскладывается на короткие шаги. Выполнил первый шаг — переходи ко второму, а в конце получаешь то, что требовалось. Для многих дел такие пошаговые инструкции уже кем-то составлены: руководство к стиральной машине, памятка по сборке мебели, правила оформления заявления на сайте.

Понятие алгоритма

Сравним три задачи, совсем не похожие друг на друга. Задача «Перевести число 25 в двоичную систему». 1) Разделить число на 2 с остатком. 2) Записать остаток. 3) Частное снова разделить на 2 и продолжать, пока частное не станет нулём. 4) Выписать остатки в обратном порядке. Получится 11001. Задача «Приготовить бутерброд». 1) Отрезать ломоть хлеба. 2) Намазать его маслом. 3) Положить сверху ломтик сыра. Задача «Узнать, делится ли число на 3». 1) Сложить все цифры числа. 2) Если сумма делится на 3, то и число делится на 3, иначе не делится.

Вычисления, кухня и признак делимости — дела разные, но устроены одинаково. Каждое описано цепочкой коротких указаний, и если выполнять эти указания точно и по порядку, получится нужный итог. Такие цепочки указаний и называют алгоритмами. Выполняет их в наших примерах человек.

Перед тем как составлять алгоритм, договариваются о двух вещах: что известно в начале (это исходные данные) и что нужно получить (это результат). Отсюда первое, пока упрощённое определение: алгоритм — это описание шагов решения задачи, которые ведут от исходных данных к результату. Общая схема показана в верхней строке рис. 1. Алгоритм бывает вычислительным, как перевод числа, и невычислительным, как бутерброд. Многие алгоритмы вы знаете с младших классов: сложение и деление столбиком, правила переноса слов, построение треугольника по трём сторонам циркулем и линейкой.

Пример 1. Этот алгоритм превращает одно натуральное число в другое: 1) перевести число в двоичную систему; 2) сосчитать единицы в двоичной записи; 3) если единиц нечётное количество, дописать к записи справа цифру 1, если чётное — цифру 0; 4) перевести полученную двоичную запись обратно в десятичную систему. Возьмём 13. В двоичной системе 13 = 1101₂, единиц три — количество нечётное, дописываем 1: 11011₂ = 16 + 8 + 2 + 1 = 27. Возьмём 12: 12 = 1100₂, единиц две, дописываем 0: 11000₂ = 24. Ответ: из 13 получается 27, из 12 — 24. Полезно заметить: дописать справа цифру к двоичной записи — всё равно что умножить число на 2 и прибавить эту цифру. Проверка: 13 · 2 + 1 = 27, 12 · 2 + 0 = 24.

Исполнитель алгоритма

Алгоритм всегда пишут для кого-то. Исполнитель — это объект, который умеет выполнять определённый набор команд. Им может быть человек, животное (дрессированная собака выполняет команды «сидеть» и «рядом») или техническое устройство.

Исполнители бывают формальными и неформальными. Формальный исполнитель не задумывается над смыслом команд и не спрашивает, зачем их выполнять; одну и ту же команду он каждый раз выполняет одинаково. Неформальный исполнитель может выполнить одну команду по-разному: человек, которого попросили «принеси что-нибудь попить», сегодня принесёт воду, а завтра сок. Калькулятор, компьютер, станок с программным управлением — формальные исполнители. Человек тоже становится формальным исполнителем, когда делит числа столбиком строго по правилу, ни на шаг от него не отступая.

Для любого формального исполнителя указывают четыре характеристики (нижняя часть рис. 1). Круг решаемых задач, или назначение, — то, для чего исполнитель создан: чертить линии, вычислять, перемещаться по полю, составлять слова из букв. Среда — условия и обстановка, в которых исполнитель действует: лист бумаги, клетчатое поле со стенами, записанное на экране число. Исходные данные и результат любого алгоритма находятся в среде того исполнителя, для которого алгоритм написан. Среду можно описать полным набором её характеристик, то есть состоянием: в какой клетке сейчас исполнитель, куда он повёрнут, какое число у него записано. Система команд исполнителя (СКИ) — все команды, которые исполнитель умеет выполнять. Алгоритм записывают только командами из этой системы, иначе исполнитель его выполнить не сможет. Режим работы. В режиме непосредственного, или ручного, управления исполнитель выполняет каждую команду сразу, как только её получил: так лампа загорается от выключателя, а телевизор переключает канал по кнопке пульта. В режиме программного управления исполнитель сначала получает всю последовательность команд — программу, а потом выполняет её сам, без вмешательства человека: так посудомоечная машина проходит выбранную программу мойки от начала до конца.

Исполнители Черепаха, Вычислитель, Конструктор и Робот

Черепаха двигается по экрану и оставляет за собой след в виде линии. Её система команд такая. Вперёд n — пройти n шагов в ту сторону, куда повёрнута голова. Направо m — повернуть голову по ходу часовой стрелки на m градусов. Есть ещё запись Повтори k [команды]: команды в квадратных скобках выполняются k раз подряд.

Пример 2. Что нарисует Черепаха по алгоритму Повтори 6 [Вперёд 30 Направо 60]?