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

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

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

4 варианта с ответами

Исполнитель преобразует число на экране. Сколько существует программ, для которых при исходном числе 19 результатом является 2, при этом траектория вычислений не содержит числа 7 и содержит 13? Траектория вычислений программы это последовательность результатов выполнения всех команд программы

Текст распознан с изображения задания. Формулы, таблицы и рисунки смотрите на картинке ниже.

ЕГЭ по информатике: задание 23, условие
Ответ
68

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

1. прибавить 1
2. умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя — последовательность команд.

Сколько существует программ, которые число 2 преобразуют в число 25?

Ответ
47

Считаем от конца к началу: пусть K(n) — число программ, переводящих n в 25.

Если n > 25, то K(n) = 0; K(25) = 1. Для остальных K(n) = K(n + 1) + K(2n), потому что из n можно пойти ровно двумя способами.

Разворачивая это правило вниз до n = 2, получаем 47. Ответ — 47.

Исполнитель преобразует число на экране. У исполнителя две команды:

1. прибавить 1
2. умножить на 2

Сколько существует программ, которые число 2 преобразуют в число 25, при этом траектория вычислений программы не содержит число 13?

Ответ
37

Правило то же: K(n) = K(n + 1) + K(2n), K(25) = 1, K(n) = 0 при n > 25.

Запрет на число 13 означает, что K(13) = 0: в эту вершину заходить нельзя, и все программы, проходящие через неё, отпадают.

С этим дополнительным условием пересчитываем значения вниз до n = 2 и получаем 37. Ответ — 37.

Исполнитель преобразует число на экране. У исполнителя две команды:

1. прибавить 2
2. умножить на 3

Сколько существует программ, которые число 1 преобразуют в число 31?

Ответ
12

Считаем так же: K(31) = 1, K(n) = 0 при n > 31, иначе K(n) = K(n + 2) + K(3n).

Обратите внимание, что прибавление двойки сохраняет чётность, а умножение на три её не меняет, поэтому из нечётного числа 1 достижимы только нечётные числа — это сильно сокращает перебор.

Доводя расчёт до n = 1, получаем 12. Ответ — 12.

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

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

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

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

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

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

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

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

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

Ответ6

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

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