Задание 13 ЕГЭ по информатике 2027: анализ хода исполнения алгоритма

Считаем количество программ динамикой, а не перебором.

Простыми словами

Исполнитель умеет две вещи — прибавить и умножить. Сколько разных программ переведут число A в число B? Перебирать программы долго; гораздо быстрее идти по числам от A к B и для каждого записывать, сколькими способами до него можно добраться.

Это тот же приём, что и подсчёт путей в графе: числа — вершины, команды — стрелки.

В 2027 году этот номер получил новую тему. Задания прошлых лет под номером 13 относились к маске подсети — не путайте источники.

Главная формула

R (v) = R (v - d) + R (\frac{v}{m})

число программ, приводящих из A в v

где $R (v)$ — число программ из A в $v$ , $d$ — шаг команды «прибавь», $m$ — множитель команды «умножь». Второе слагаемое берётся, только если $v$ делится на $m$ нацело и частное не меньше A. База: $R (A) = 1$ ; для чисел меньше A — $0$ .

Почему так: последняя команда программы — либо «прибавь» (тогда до неё было $v - d$ ), либо «умножь» (тогда было $v / m$ ). Эти случаи не пересекаются, поэтому их количества складываются.

Разбор: из 2 в 12

Команды: 1) прибавь 1, 2) умножь на 2. Сколько программ переводят 2 в 12?

Внизу — число

v

, в ячейке —

R (v)

. В 12 ведут стрелки из 11 и из 6:

R (12) = 7 + 3 = 10

$R (2) = 1$ , $R (3) = R (2) = 1$ (3 нечётное — только +1).
$R (4) = R (3) + R (2) = 2$ ; $R (5) = 2$ ; $R (6) = R (5) + R (3) = 3$ ; $R (7) = 3$ .
$R (8) = R (7) + R (4) = 5$ ; $R (9) = 5$ ; $R (10) = R (9) + R (5) = 7$ ; $R (11) = 7$ .
$R (12) = R (11) + R (6) = 7 + 3 = 10$ . Ответ: 10.

Обязательные и запрещённые числа

Траектория содержит CСчитаем A → C и C → B отдельно и перемножаем: каждая первая половина сочетается с каждой второй. Через 6:

R_{2 \to 6} \cdot R_{6 \to 12} = 3 \cdot 2 = 6

Траектория не содержит CСтавим

R (C) = 0

и считаем дальше как обычно. Без 6: получится

4

. Проверка:

6 + 4 = 10

✓

def f(a, b):
    if a > b: return 0
    if a == b: return 1
    return f(a + 1, b) + f(a * 2, b)

print(f(2, 12))             # 10
print(f(2, 6) * f(6, 12))   # через 6: 6

Рекурсия идёт от начала: из $a$ можно перейти в $a + 1$ или $2 a$ . Для «не содержит C» добавьте строку if a == c: return 0.

Где теряют балл: берут слагаемое $R (v / m)$ , когда $v$ не делится на $m$ или частное меньше A; для «содержит C» складывают вместо умножения; не обнуляют запрещённое число.

Где эта тема разобрана подробно

Алгоритмы и исполнителиИзучить →

Примеры заданий 13 ЕГЭ по информатике

Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.

Исполнитель преобразует число на экране. У исполнителя две команды, каждой присвоен номер:
1) прибавь 2
2) умножь на 2
Первая команда увеличивает число на экране на 2, вторая умножает его на 2. Программа для исполнителя — это последовательность номеров команд. Сколько существует программ, которые число 2 преобразуют в число 118?

Показать ответ

Ответ: 1294
Решение.

Обозначим R(v) — число программ, приводящих из 2 в v. Тогда R(v) = R(v − 2) + R(v / 2), причём второе слагаемое берётся, только если v делится на 2.
v 2 3 4 5 6 7 8 9
R(v) 1 0 2 0 2 0 4 0
Продолжая до v = 118, получаем 1294.

v	2	3	4	5	6	7	8	9
R(v)	1	0	2	0	2	0	4	0

Исполнитель преобразует число на экране. У исполнителя две команды, каждой присвоен номер:
1) прибавь 2
2) умножь на 3
Первая команда увеличивает число на экране на 2, вторая умножает его на 3. Программа для исполнителя — это последовательность номеров команд. Сколько существует программ, которые число 3 преобразуют в число 107, при этом траектория вычислений не содержит числа 50? Траектория — это последовательность результатов всех команд программы.

Показать ответ

Ответ: 65
Решение.

Считаем по формуле R(v) = R(v − 2) + R(v / 3) (второе слагаемое — только если v делится на 3).
R(3) = 1, а R(50) = 0 — через это число ходить нельзя.
Доводя счёт до 107, получаем 65 программ (без запрета их было бы 65).

Исполнитель преобразует число на экране. У исполнителя две команды, каждой присвоен номер:
1) прибавь 1
2) умножь на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя — это последовательность номеров команд. Сколько существует программ, которые число 3 преобразуют в число 50, и при этом траектория вычислений содержит число 21?

Показать ответ

Ответ: 108
Решение.

Любая такая программа распадается на две независимые части: 3 → 21 и 21 → 50.
Программ из 3 в 21: 18. Программ из 21 в 50: 6.
Общее число: 18 × 6 = 108.

Анализ хода исполнения алгоритма

Простыми словами

Главная формула

Разбор: из 2 в 12

Обязательные и запрещённые числа

Где эта тема разобрана подробно

Примеры заданий 13 ЕГЭ по информатике