Алгоритмы и исполнители: что это такое
Алгоритм — это понятное и точное предписание исполнителю: какие действия выполнить и в каком порядке, чтобы из исходных данных получить результат. Исполнитель — тот, кто эти действия выполняет: человек, робот, компьютер или условный «Вычислитель» из задачи.
У каждого исполнителя есть система команд — полный набор действий, которые он умеет делать. Ничего другого он не сделает. Если у Вычислителя есть команды «прибавить 1» и «умножить на 2», вычесть число он не сможет.
Свойства алгоритма:
- дискретность: алгоритм разбит на отдельные шаги;
- понятность: в нём есть только команды из системы команд исполнителя;
- определённость: каждый шаг однозначен, поэтому два исполнителя при одинаковых данных получат одинаковый результат;
- результативность: за конечное число шагов алгоритм заканчивается;
- массовость: он подходит не для одного числа, а для целого класса данных.
Какие исполнители встречаются в заданиях
В школьных заданиях исполнители обычно вымышленные, но устроены одинаково: есть начальное состояние, команды и вопрос о результате.
- Вычислитель преобразует число на экране. Команды вроде «прибавить 2» или «умножить на 2». Спрашивают, какая программа переведёт 1 в 42, или сколько существует таких программ.
- Редактор работает со строкой цифр. Команда заменить (v, w) заменяет первое слева вхождение цепочки v на w. Часто в алгоритме есть цикл ПОКА, а вопрос про итоговую строку. Со строками связана тема массивы и строки.
- Черепаха ходит по плоскости с координатами и оставляет след. Команды «Вперёд n», «Направо m», «Повтори k раз». Просят найти, сколько точек с целыми координатами лежит внутри фигуры или внутри пересечения двух фигур.
- Исполнитель на карте (робот, корабль) двигается по клеткам и не проходит через препятствия. Спрашивают про самый короткий или самый длинный путь.
Отдельно идут задания на трассировку: по алгоритму с переменными заполняют таблицу значений. Это основа для темы основы программирования.
Как решать задачи про исполнителя: разбор
Задача. У исполнителя две команды: 1 — прибавить 1, 2 — умножить на 2. Сколько существует программ, которые преобразуют число 1 в число 6?
Перебирать программы руками долго, поэтому считаем с конца.
- Обозначь f(n) число программ, переводящих 1 в n.
- Подумай, какой могла быть последняя команда. Либо «прибавить 1» (тогда до неё было n − 1), либо «умножить на 2» (тогда было n ÷ 2, это возможно только для чётного n).
- Значит, для чётного n: f(n) = f(n − 1) + f(n ÷ 2), для нечётного n: f(n) = f(n − 1).
- Начало: f(1) = 1, это пустая программа.
- Считаем по порядку: f(2) = f(1) + f(1) = 2; f(3) = f(2) = 2; f(4) = f(3) + f(2) = 4; f(5) = f(4) = 4; f(6) = f(5) + f(3) = 6.
Ответ: 6. Проверка на малом числе: в 2 из единицы ведут две программы, «прибавить 1» и «умножить на 2», и f(2) = 2 это подтверждает. Такой подсчёт через предыдущие значения родственен рекурсии и обычному перебору в комбинаторике.
Другой тип: найти начальное значение. Алгоритм: a := x; b := a * 2 + 5; a := a + b. В конце a = 20. После первой строки a = x, после второй b = 2x + 5, после третьей a = x + 2x + 5 = 3x + 5. Из 3x + 5 = 20 получаем x = 5.
Где ошибаются чаще всего
- Путают номер команды и её действие. В программе записаны номера, например 1 2 2 1. Сначала выпиши, что каждый номер значит, и только потом считай.
- Не проверяют ограничения. Если у команды в условии есть оговорка, к каким числам её можно применять, проверяй её на каждом шаге. Иначе в ответ попадут программы, которые исполнитель выполнить не может.
- Неправильно читают Редактор. Команда заменить меняет только первое слева вхождение, а не все. Цикл ПОКА проверяет условие до каждого повтора: если оно ложно сразу, тело цикла не выполнится ни разу.
- Ошибаются с направлением у Черепахи. Сначала она смотрит вдоль положительного направления оси ординат, то есть вверх, а «Направо» поворачивает её по часовой стрелке. Нарисуй путь на клетчатой бумаге и отметь, попадают ли точки на границе фигуры в ответ: это зависит от условия.
- Идут от начала там, где проще с конца. В задачах на количество программ и на «найти начальное значение» обратный ход почти всегда короче.
Какие задания присылают ученики
По теме на сайте 19 заданий для 8–11 классов. Больше всего задач про Черепаху: анализ алгоритма и подсчёт точек внутри пересечения или объединения фигур. Есть подсчёт программ для Вычислителя, задачи про Редактор с циклом ПОКА, трассировка переменных, поиск пути по карте и вопросы про циклические алгоритмы.
Найди в списке выше задание, похожее на твоё, и сравни ход решения со своим. Если подходящего нет, сфотографируй условие и отправь на сайт: придёт решение с пошаговым разбором.