10 XP
ЕГЭ · Информатика · задание 231 балл · ≈10 мин

Задание 23 ЕГЭ: Исполнитель и количество программ

У исполнителя две команды: прибавить 1 и умножить на 2; нужно посчитать, сколько разных программ переводят число A в число B, иногда с запретом проходить через заданное число. Перебирать программы нельзя — их экспоненциально много, зато таблица значений R(n) заполняется по одному числу за шаг: в чётное n попадаем из n-1 командой +1 или из n/2 командой ×2. Типичная потеря балла — неверная база и запрет: R(A) равен единице, а запрещённому числу ставится ноль, и тогда все пути через него гаснут.

Все задания Информатика

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

Динамическое программирование. Это задание с коротким ответом, который проверяется автоматически. Одна арифметическая ошибка — ноль баллов, поэтому скорость и аккуратность здесь важнее гениальности.

Формулы к заданию

База: в начальное число ведёт одна пустая программа
Чётное n: последняя команда либо +1, либо ×2
Нечётное n: умножение на 2 не может дать нечётный результат

Разбор типовых задач

Пример 1

Исполнитель преобразует число командами «прибавить 1» и «умножить на 2». Сколько существует программ, переводящих число 1 в число 10?

Решение по шагам
  1. Идём от начала: R(1) = 1 — база; для чётных n складываем R(n-1) и R(n/2), для нечётных берём только R(n-1).
  2. R(2) = R(1) + R(1) = 2, R(3) = 2, R(4) = R(3) + R(2) = 4, R(5) = 4.
  3. R(6) = R(5) + R(3) = 4 + 2 = 6, R(7) = 6, R(8) = R(7) + R(4) = 6 + 4 = 10, R(9) = 10.
  4. Финальный шаг: R(10) = R(9) + R(5) = 10 + 4 = 14 — столько программ доводят 1 до 10.

Ответ: 14

Пример 2

Тот же исполнитель с командами «прибавить 1» и «умножить на 2». Сколько программ переводят число 3 в число 10? Используйте метод «от конца».

Решение по шагам
  1. Ставим в 10 единицу: N(10) = 1, и спускаемся от конца к началу; N(n) — число программ из n в 10.
  2. Пока удвоение выводит за 10, работает только +1: N(9) = 1, N(8) = 1, N(7) = 1, N(6) = 1.
  3. Дальше подключаются удвоения: N(5) = N(6) + N(10) = 2, N(4) = N(5) + N(8) = 2 + 1 = 3.
  4. Старт: N(3) = N(4) + N(6) = 3 + 1 = 4 — столько программ переводят 3 в 10.

Ответ: 4

Пример 3

Сколько существует программ, переводящих число 2 в число 20 командами «прибавить 1» и «умножить на 2», если траектория не должна проходить через число 10?

Решение по шагам
  1. База R(2) = 1, а запрещённому числу ставим ноль: R(10) = 0 — через него не пройдёт ни одна программа.
  2. Заполняем до запрета: R(3) = 1, R(4) = R(3) + R(2) = 2, R(5) = 2, R(6) = 2, R(7) = 2, R(8) = R(7) + R(4) = 4, R(9) = 4.
  3. После нуля значения восстанавливаются: R(11) = 0, R(12) = R(11) + R(6) = 2, R(13) = 2, R(14) = 2, R(15) = 2, R(16) = R(15) + R(8) = 6, R(17) = 6, R(18) = 6, R(19) = 6.
  4. Финал: R(20) = R(19) + R(10) = 6 + 0 = 6; запрет отрезал все программы, где удвоение давало ровно 10.

Ответ: 6

Тренажёр задания (числа меняются)

Клавиши 1–9 выбирают вариант, Enter — «Проверить»

Число 2 обрабатывают программой, в которой 2 команд «умножить на 2» и 3 команд «прибавить 1»; сначала идут все умножения, затем все прибавления. Какое число получится в конце?

Каждая команда исполнителя — одна из двух: «прибавить 1» или «умножить на 2». Сколько существует различных программ из 4 команд?

Программа исполнителя состоит из 3 команд «прибавить 1» и ровно одной команды «умножить на 2». Сколько существует различных программ такого состава?

Из числа 1 получили число N программой из 4 команд: 2 команд «умножить на 2» и остальные — «прибавить 1»; сначала идут все умножения, затем все прибавления. Чему равно N?

Сколько программ переводят число 1 в число 6 исполнителя с командами «прибавить 1» и «умножить на 2»?

Если число B нечётное, то последней командой любой программы, переводящей A в B, может быть только «прибавить 1».

Число 2 обрабатывают программой, в которой 2 команд «умножить на 2» и 2 команд «прибавить 1»; сначала идут все умножения, затем все прибавления. Какое число получится в конце?

Каждая команда исполнителя — одна из двух: «прибавить 1» или «умножить на 2». Сколько существует различных программ из 2 команд?

Типичные ошибки

  • Ставят в запрещённое число единицу вместо нуля — тогда пути через него ошибочно засчитываются.
  • Пишут в базу ноль: в начальное число ведёт ровно одна пустая программа, поэтому R(A) = 1.
  • Для нечётного n прибавляют R(n/2): деление на 2 не даёт целого числа, такого слагаемого в формуле нет.
  • Считают программы для «не более чем k команд», когда спрашивают «ровно k команд», или наоборот.

Повторить теорию по информатике

Разбор задания опирается на формулы и приёмы — если тема вспоминается с трудом, сначала пробегите уроки:

Формат задания 23 на экзамене

Балл за задание: 1. Ориентир по времени: ≈10 минут вместе с оформлением решения. Проверяемая тема: динамическое программирование. На тренировке лимитов нет — сначала точность, скорость придёт после 10–15 решённых задач. Планируйте экзамен так, чтобы не застревать: если решение не идёт — зафиксируйте промежуточный результат, переходите дальше и возвращайтесь в конце, потому что остальные задания дадут больше суммарных баллов.

Частые вопросы про задание 23

Как решать задание 23 ЕГЭ по информатике?

Строй таблицу значений от A до B: для каждого числа смотри, из какого числа приходим командой +1 и из какого — командой ×2, и складывай количества программ. Ответом будет значение в клетке B, и никакого перебора программ не понадобится.

Что делать, если траектория не должна проходить через число C?

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

Почему метод «от конца» быстрее полного перебора?

Каждое значение считается один раз из уже готовых соседних, поэтому вместо экспоненциального числа программ ты обрабатываешь лишь числа от A до B. На отрезке в пару десятков чисел это секунды работы даже вручную.

Похожие задания