Задание 23 ЕГЭ по информатике

Что проверяет: Количество программ исполнителя

Задание 23 ЕГЭ по информатике проверяет тему «количество программ исполнителя». Ниже вы найдёте 1 вариант с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.

Ответ

Теория к заданию 23 ЕГЭ по информатике: количество программ исполнителя

Нужно посчитать число программ, переводящих одно число в другое, с ограничениями на траекторию.

Что нужно знать

Задача решается динамическим программированием по значениям: количество программ из a в b равно сумме количеств программ из всех достижимых за один ход состояний.
Запрещённое число исключают из перебора: количество программ через него равно нулю.
Обязательное число разбивает путь на два независимых участка: из начала в него и из него в конец, результаты перемножаются.
Команды могут и увеличивать, и уменьшать число; направление задаётся условием.
Базовый случай: количество программ из числа в него же равно единице.

Подсчёт числа программ

Число программ из числа a в число b считается динамическим программированием: N(b) = сумма N(предшественников).
Если есть команды «прибавить 1» и «умножить на 2», то N(x) = N(x−1) + N(x/2), причём второе слагаемое только для чётных x.
Базовый случай: N(старт) = 1.
Запрет на прохождение через число обнуляет N в этой точке: просто ставим ноль и идём дальше.
Обязательное прохождение через число k: считаем отдельно путь от старта до k и от k до финиша, затем перемножаем.
Таблицу удобно заполнять слева направо: к моменту вычисления N(x) все меньшие значения уже известны.
Проверяйте, входит ли стартовое число в диапазон запрета.
Ответ обычно небольшое целое число, помещающееся в таблицу из 20-30 строк.

Как решать задание 23

Разбейте задачу на участки по обязательным числам.
Для каждого участка постройте таблицу количества программ по возрастанию или убыванию значений.
Обнуляйте ячейки, соответствующие запрещённым числам.
Перемножьте количества по участкам.
Запишите итоговое число.

Разбор примера

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

Заводим таблицу N(x), где хранится число программ из 1 в x. Базовый случай: N(1) = 1.
N(2) = N(1) + N(1) = 1 + 1 = 2 (прибавить 1 к единице или умножить единицу на 2).
N(3) = N(2) = 2, потому что 3 нечётное и умножением его не получить.
N(4) = N(3) + N(2) = 2 + 2 = 4.
N(5) = N(4) = 4.
N(6) = N(5) + N(3) = 4 + 2 = 6.

Ответ6

Частые ошибки

Складывают количества по участкам вместо умножения.
Забывают исключить запрещённое число.

Задание 23 входит в ЕГЭ по информатике. На этой странице собраны все варианты этого номера, которые разобраны на сайте: условие, правильный ответ и разбор решения. Остальные номера открываются в списке выше, а целиком все задания ЕГЭ по информатике с ответами собраны на странице предмета.