23 задание ЕГЭ информатика
Количество программ исполнителя
1 балл ≈ 8 мин уровень П Анализ исполнения алгоритма (число программ)
Задание 23 – исполнитель с двумя-тремя командами (прибавить, умножить, вычесть, разделить нацело). Найти количество программ, переводящих число a в b, при условиях на траекторию: содержит число c, не содержит число d. 1 балл.
Рекурсия
def cnt(a, b):
if a > b: # «перелетели» (для возрастающих команд)
return 0
if a == b:
return 1
return cnt(a + 1, b) + cnt(a * 2, b)
# из 1 в 20, траектория содержит 10, не содержит 15:
print(cnt(1, 10) * cnt(10, 20))Условия на траекторию
- «Содержит c» – произведение: cnt(a, c) · cnt(c, b).
- «Не содержит d» – добавь в функцию: if a == d: return 0 (или a > b or a == d).
- Для убывающих команд (вычесть, разделить) поменяй условие выхода: if a < b: return 0.
Разобранный пример. Команды: +1, ×2. Сколько программ переводят 1 в 20, проходя через 10? cnt(1, 10) = 14, cnt(10, 20) = 2 (×2 или десять раз +1). Ответ: 14 · 2 = 28.
Для команды «целая часть от деления на 3» число может уменьшаться быстро: из 19 через «:3» в 6. Пиши условие a < b: return 0 для убывающего исполнителя и проверяй, что команда действительно меняет число (иначе бесконечная рекурсия, например 1 // 3 = 0, 0 // 3 = 0).
Ловушки: «содержит c» и «не содержит d» одновременно – запрет d должен действовать в обеих частях; программа длины 0 (a == b сразу) обычно не считается, если a ≠ b; деление нацело в Python – //.
- «Содержит» = умножение двух подсчётов, «не содержит» = return 0 на запретном числе.
- Для больших чисел добавь @lru_cache – рекурсия станет мгновенной.
- Проверь функцию на маленьком примере, посчитав вручную.
Разобранные задания 23 из открытого банка ФИПИ
Пример 1 · код ФИПИ F27CB9
Исполнитель Вычислитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 2.
Программа для Вычислителя это последовательность команд.
Сколько существует таких программ, которые исходное число 4 преобразуют в число 13, и при этом траектория вычислений программы содержит число 11?
Траектория вычислений программы это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
Показать ответ и решение
Ответ: 50
(4 → 11) × (11 → 13) по командам +1, +2, ×2: .
Пример 2 · код ФИПИ De167D
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 3
C. Найти целую часть от деления на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория вычислений не содержит числа 9 и содержит 12?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 13 траектория состоит из чисел 6, 3, 2.
Показать ответ и решение
Ответ: 153
Пути 19→12, умноженные на пути 12→3 без числа 9 (динамика). Итого 153.
Пример 3 · код ФИПИ DE8735
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 2
Первая из них увеличивает число на экране на 2, вторая увеличивает число на экране в два раза.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 52, и при этом траектория вычислений содержит число 18?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 3 траектория будет состоять из чисел 5, 10, 12.
Показать ответ и решение
Ответ: 96
Путь 1 → 18 → 52 командами +2, ×2.
Считаем динамикой (число путей до каждого числа), перемножая количества на участках до и после обязательных чисел: 96.
Частые вопросы о задании 23
Сколько баллов даёт задание 23 ЕГЭ по информатике?
Максимум – 1 первичный балл. Норма времени на экзамене – около 8 мин. Уровень сложности – П.
Что проверяет задание 23?
Задание 23 – исполнитель с двумя-тремя командами (прибавить, умножить, вычесть, разделить нацело). Найти количество программ, переводящих число a в b, при условиях на траекторию: содержит число c, не содержит число d. 1 балл.
Как подготовиться к заданию 23?
Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.