Задание 6: исполнители и анализ программы с циклом

Задание 6 (базовый уровень): что сделает исполнитель и сколько программ приводят к нужному результату.

Исполнитель — это абстрактное устройство с фиксированным набором команд (двигаться, умножать, рисовать). Задание 6 проверяет умение проследить выполнение программы с циклом и анализировать её результат.

Что проверяет задание

Даётся исполнитель (например, Чертёжник, перемещающийся по координатам, или числовой автомат с командами вроде «прибавь 3», «умножь на 2») и программа с циклом. Вопросы бывают двух типов: «какой результат даст программа» (прямое моделирование) и «сколько различных программ из заданных команд приводят из A в B» (перебор/подсчёт путей). Оба идеально ложатся на Python.

Тип 1: прямое моделирование цикла

Если в задании дан конкретный код исполнителя с циклом, проще всего повторить его на Python и посмотреть результат. Пусть Чертёжник стартует в точке (0, 0) и выполняет программу: «повторить 4 раза: сместиться на (2, 1)», затем «сместиться на (−3, 5)».

x, y = 0, 0
# повторить 4 раза: сдвиг на (2, 1)
for _ in range(4):
    x += 2
    y += 1
# затем один сдвиг на (-3, 5)
x += -3
y += 5
print("итоговая точка:", (x, y))

Вывод:

итоговая точка: (5, 9)

Моделирование исключает арифметические ошибки: где бы ни было сложение или вычитание, машина считает точно. Если в исполнителе есть условие внутри цикла — переносите его в код один в один.

Тип 2: подсчёт числа программ

Самая частая разновидность: «У исполнителя две команды: 1) прибавь 3; 2) умножь на 2. Сколько различных программ переводят число 2 в число 25?» Здесь нужно перебрать все последовательности команд. Удобно — поиск в ширину (BFS): из каждого числа пробуем обе команды, считаем, сколько путей доходят до цели.

from collections import deque

start, goal = 2, 25

def count_programs(start, goal):
    count = 0
    queue = deque([(start, 0)])         # (текущее число, длина программы)
    while queue:
        value, steps = queue.popleft()
        if value == goal:
            count += 1
            continue
        if value > goal or steps > 20:  # отсекаем перелёт и слишком длинные
            continue
        queue.append((value + 3, steps + 1))   # команда 1: +3
        queue.append((value * 2, steps + 1))   # команда 2: *2
    return count

print("программ, ведущих 2 -> 25:", count_programs(start, goal))

Вывод:

программ, ведущих 2 -> 25: 6

Важно отсекать ветви, где число уже превысило цель (value > goal): команды только увеличивают число, поэтому из «перелёта» вернуться нельзя, и такие пути считать бессмысленно. Без отсечения перебор был бы бесконечным.

Альтернатива: рекурсивный подсчёт

Тот же подсчёт можно записать короткой рекурсией — она часто понятнее и так же надёжна:

def count(value, goal):
    if value == goal:
        return 1            # дошли — это одна программа
    if value > goal:
        return 0            # перелёт — тупик
    # пробуем обе команды и складываем числа способов
    return count(value + 3, goal) + count(value * 2, goal)

print("программ 2 -> 25:", count(2, 25))

Вывод:

программ 2 -> 25: 6

Эта рекурсия — мостик к заданию 16: тот же приём «число способов = сумма способов из достижимых состояний» лежит в основе всех задач на подсчёт путей.

Вариант с тремя командами и «запретным» числом

Часто условие усложняют: добавляют третью команду и/или запрещают проходить через определённое число. Например: «Команды: +1, +2, ·3. Сколько программ переводят 1 в 20, не проходя через число 7?» Запрет — это просто дополнительное отсечение в рекурсии:

def count(value, goal, forbidden):
    if value == forbidden:
        return 0                # через запретное число нельзя
    if value == goal:
        return 1
    if value > goal:
        return 0
    return (count(value + 1, goal, forbidden)
            + count(value + 2, goal, forbidden)
            + count(value * 3, goal, forbidden))

print("программ 1 -> 20, минуя 7:", count(1, 20, 7))

Вывод:

программ 1 -> 20, минуя 7: 3444

Запрет «не проходить через 7» добавляется одной строкой if value == forbidden: return 0. Это типовое усложнение задания 6 — и оно же встречается в задании 23 (Часть 2), где путей бывают тысячи. Освоив приём здесь, вы готовы к более тяжёлым версиям.

Типичные ловушки

Отсечение перелёта. Если команды только увеличивают значение, обязательно обрывайте ветви, где значение превысило цель, — иначе перебор не остановится.
Порядок команд важен. «+3 потом ·2» и «·2 потом +3» — это разные программы, обе нужно учесть.
Считаем программы, а не числа. Вопрос обычно про количество последовательностей команд, а не про множество достижимых чисел.
Координаты Чертёжника. Следите за знаками смещений и за тем, сколько раз выполняется тело цикла.

Итог

«Что получится» — повторите программу исполнителя на Python один в один.
«Сколько программ A → B» — перебор (BFS или рекурсия), складывая числа способов из достижимых состояний.
Если команды монотонно увеличивают значение, отсекайте «перелёт» — иначе перебор не завершится.