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

Задание 23 ЕГЭ: Количество программ: +1 и умножение на 2

У исполнителя две команды: прибавить 1 и умножить на 2. Нужно посчитать, сколько разных программ переводят число s в число t — иногда с обязательным проходом через заданную точку или с запретом. Метод всегда одинаков: идём от старта к финишу и для каждого числа считаем, сколько программ в него приходит — сумма по всем предшественникам. Предшественники числа x — это x − 1 (команда +1) и x/2 (команда ×2, только для чётных x, больших старта). Теряют балл, когда учитывают умножение из точки меньше старта или забыть вычесть пути через запретную точку.

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

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

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

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

В стартовую точку одна «пустая» программа
Для чётных x: предшественники x − 1 и x/2
Для нечётных x: приходит только из x − 1
Программы через p — произведение программ двух участков

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

Пример 1

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

Решение по шагам
  1. Заполняем таблицу от 2 до 10. N(2) = 1 — старт.
  2. Нечётные числа приходят только сложением: N(3) = N(2) = 1, N(5) = N(4) = 2, N(7) = N(6) = 3, N(9) = N(8) = 5.
  3. Чётные — сложение плюс умножение: N(4) = N(3) + N(2) = 1 + 1 = 2; N(6) = N(5) + N(3) = 2 + 1 = 3.
  4. N(8) = N(7) + N(4) = 3 + 2 = 5; N(10) = N(9) + N(5) = 5 + 2 = 7.
  5. Ответ: 7 программ. Контроль перебором: 2→3→4→5→6→7→8→9→10, 2→4→5→6→7→8→9→10, 2→3→6→7→8→9→10 и ещё четыре с умножениями на конце.

Ответ: 7

Пример 2

Сколько программ переводят 2 в 10 и проходят обязательно через число 6?

Решение по шагам
  1. Разбиваем маршрут на два участка: 2 → 6 и 6 → 10.
  2. Уже посчитано: N(6) = N(5) + N(3) = 2 + 1 = 3.
  3. Считаем второй участок от 6: M(6) = 1; M(7) = M(6) = 1; M(8) = M(7) = 1 (предшественник 4 < 6 не учитываем); M(9) = M(8) = 1; M(10) = M(9) = 1.
  4. Перемножаем: 3 · 1 = 3.
  5. Проверка перебором: 2→3→4→5→6→7→8→9→10, 2→4→5→6→7→8→9→10, 2→3→6→7→8→9→10 — ровно три.

Ответ: 3

Пример 3

Сколько программ переводят 2 в 10, НЕ проходя через число 6?

Решение по шагам
  1. Всего программ из 2 в 10: 7 (посчитано ранее).
  2. Через 6 проходит 3 программы (посчитано ранее).
  3. Вычитаем: 7 − 3 = 4.
  4. Проверка: программы, идущие мимо 6, должны избегать и умножения 3→6, и цепочки сложений до 6. Это 2→4→8→9→10, 2→3→4→8→9→10, 2→4→5→10? — нет, 5·2 = 10 подходит: 2→4→5→10, и 2→4→8→9→10, 2→3→4→8→9→10, 2→3→4→5→10 — суммируем: 4 маршрута.

Ответ: 4

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

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

Исполнитель умеет +1 и ×2. Сколько программ переводят 1 в 7?

Исполнитель умеет +1 и +2. Сколько программ переводят 1 в 7? (числа Фибоначчи по построению)

Исполнитель умеет только +1. Сколько программ переводят 9 в 17?

Исполнитель умеет +1 и ×2. Сколько программ переводят 2 в 10 через 6? (участки считаются независимо и перемножаются)

Исполнитель умеет +1 и ×2. Какие предшественники есть у чётного числа x при подсчёте программ из старта s, если s < x/2?

Чтобы посчитать программы из s в t с запретом точки p, из общего числа программ вычитают программы, проходящие через p.

Исполнитель умеет +1 и ×2. Сколько программ переводят 1 в 7?

Исполнитель умеет +1 и +2. Сколько программ переводят 1 в 7? (числа Фибоначчи по построению)

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

  • Учитывают умножение x/2 → x там, где x/2 меньше старта: такая программа не существует, путь не может начинаться ниже s.
  • Считают программы через точку p как N(p) + что-то: правильно умножать N(s→p) на число программ от p до t.
  • При подсчёте «мимо p» забывают вычесть и короткие маршруты через умножение: пересчитывай предшественников аккуратно.
  • Заполняют таблицу не по возрастанию: порядок строго от старта вверх, иначе часть слагаемых ещё не посчитана.

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

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

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

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

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

Как посчитать количество программ из 2 в 10 у исполнителя +1 и ×2?

Таблица по возрастанию: N(2) = 1, нечётные берут значение слева, чётные — сумму слева и половины. N(10) = 7.

Как посчитать программы, проходящие через заданное число?

Разбей маршрут на два участка и перемножь количества: N(s→p) · N(p→t).

Почему предшественник x/2 учитывается только у чётных чисел?

Умножение на 2 даёт только чётные результаты, поэтому в нечётное число умножением попасть нельзя.

Как посчитать программы, не проходящие через p?

Посчитай все программы из s в t, затем программы через p, и вычти второе из первого.

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