Алгоритмы и работа исполнителя

Алгоритм задаёт понятную исполнителю последовательность действий для решения класса задач. На ОГЭ нужно читать словесные записи, блок-схемы и программы, прослеживать изменение переменных и определять возможные входные или выходные данные.

• выписывайте значения переменных после каждой команды;
• в ветвлении выполняется только выбранная ветвь;
• перед каждой итерацией цикла заново проверяется условие;
• подпрограмма решает отдельную часть задачи;
• входные данные должны удовлетворять ограничениям алгоритма;
• обратный поиск ответа всегда подтверждайте прямой подстановкой.

У корректного алгоритма выделяют несколько свойств:

• дискретность: решение разбито на отдельные шаги;
• понятность: каждая команда входит в систему команд исполнителя;
• определённость: при одних и тех же данных команда трактуется одинаково;
• конечность и результативность: после конечного числа шагов получается требуемый результат;
• массовость: алгоритм применим к целому классу допустимых входных данных.

Например, команда «немного увеличьте число» неопределённа. Команда «прибавьте $2$» однозначна.

Алгоритм можно представить словами, блок-схемой или программой. В блок-схеме прямоугольник обозначает действие, ромб — проверку условия, овал — начало или конец, параллелограмм — ввод или вывод. Стрелки задают порядок переходов.

Разные формы могут описывать один процесс. Словесная команда «если число отрицательное, заменить его противоположным» в Python выглядит так:

if x < 0:
    x = -x

Следование выполняет команды одну за другой. Ветвление выбирает действие по условию. Цикл повторяет действия, пока выполняется условие или пока не завершён заданный диапазон.

Пример трассировки:

x = 5
x = x + 3
x = x * 2
print(x)

После первой команды $x=5$, затем $x=8$, в конце $x=16$. Правая часть присваивания вычисляется по старому значению, после чего результат записывается в переменную.

Инвариант — утверждение, которое остаётся верным до и после каждой итерации. В алгоритме суммирования первых $n$ натуральных чисел после обработки числа $k$ переменная total равна сумме от $1$ до $k$.

n = int(input())
total = 0
for k in range(1, n + 1):
    total += k
print(total)

Для $n=4$ значения total последовательно равны $1$, $3$, $6$, $10$. Цикл завершается, потому что диапазон содержит конечное число значений.

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

def is_even(x):
    return x % 2 == 0

print(is_even(14))

Функция возвращает True, потому что остаток от деления $14$ на $2$ равен нулю.

Исполнитель характеризуется средой, системой команд, допустимыми состояниями и правилами выполнения. Если команда не входит в систему команд или её нельзя выполнить в текущем состоянии, возникает отказ. Например, Робот не может пройти через стену. Поэтому алгоритм должен учитывать не только цель, но и ограничения среды.

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

1. выделите допустимое множество входов;
2. разберите ветви и циклы;
3. составьте таблицу «вход — промежуточные значения — выход»;
4. выберите нужный результат;
5. подставьте найденный вход в программу ещё раз.

Рассмотрим алгоритм:

x = int(input())
if x % 2 == 0:
    y = x // 2
else:
    y = 3 * x + 1
print(y)

Для разрешённых входов $2,3,4,5$ получаем:

Если в условии сказано, что вход выбирают только из этого множества, выход $10$ возможен при $x=3$. Без ограничения на вход ответ мог бы быть другим: область допустимых данных — часть задачи.

Перед трассировкой определите, когда проверяется условие. В цикле while оно проверяется до тела:

x = 20
count = 0
while x > 3:
    x //= 2
    count += 1
print(x, count)

Трасса: $(20,0)\to(10,1)\to(5,2)\to(2,3)$. Затем условие $2>3$ ложно. Программа выводит 2 3.

Система управления получает информацию о состоянии объекта и формирует воздействие. Сигнал передаёт данные или команду. В цифровой системе сигнал часто кодируется числами, но физически это может быть напряжение, свет или радиоволна.

Датчик измеряет величину: температуру, расстояние, освещённость. Исполнительное устройство изменяет объект: включает нагреватель, поворачивает двигатель, открывает клапан.

При обратной связи результат воздействия снова измеряется и влияет на следующее действие. Термостат поддерживает температуру $22\ ^\circ\mathrm{C}$:

• если температура ниже $21\ ^\circ\mathrm{C}$, нагреватель включается;
• если температура выше $23\ ^\circ\mathrm{C}$, нагреватель выключается;
• внутри промежутка текущее состояние сохраняется.

Разные пороги включения и выключения защищают систему от слишком частого переключения. Это полезное пояснение принципа; конкретные пороги всегда задаются условием задачи.

Без обратной связи устройство выполняет заранее заданные команды и не проверяет результат. Например, таймер включает полив на пять минут независимо от влажности почвы.

• Все ли команды понятны выбранному исполнителю?
• Выписаны ли начальные значения переменных?
• Условие цикла проверено перед каждой итерацией?
• Учтены ли ограничения на входные данные?
• Обратный ответ подтверждён прямым запуском?
• В системе управления различены датчик, управляющее устройство и исполнительный механизм?

Содержание тем 3.1, 3.4 и 3.6 сверено с проектом кодификатора ОГЭ-2027 ФИПИ. Синтаксис программ сверяется с официальным учебником Python. Примеры составлены FastLearn.