Я сдавал ЕГЭ по информатике в прошлом году. Сейчас я учусь в университете МИРЭА на направлении, связанном с программированием. В рубрике #хакнем_информатика продолжаю разбирать задачи из ЕГЭ по информатике. В этой статье я разберу одно из самых простых, по моему мнению, заданий — 23.
Суть задания: Вам говорят, что есть некая программа для исполнителя, и у этого исполнителя есть несколько команд (чаще всего две). Эти команды обычно простые: прибавить 1, прибавить 2, умножить на 3 и т.д.
А найти в этом задании нужно количество программ, которые приведут исполнителя из числа A в число Б. Например, из числа 2 в 12.
Конечно, можно решать это задание «руками», никто не запрещает. Но так как мы с вами люди умные, мы не будем тратить время на такое простое задание, и просто напишем небольшую программу, которая выдаст нам ответ. Писать будем на Python.
Пример 1.
Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Программа для исполнителя Калькулятор —это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
В качестве решения предлагаю такую программу:
Ответ: 13.
И так решаются все 23 задачи в ЕГЭ по информатике. Чтобы это доказать, приведу решения ещё нескольких примеров.
Пример 2.
Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
Программа для исполнителя Калькулятор —это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 13 и при этом траектория вычислений содержит число 7?
Решение в 5 строк:
Ответ: 169.
Пример 3. Программа не меняется, а время решения руками увеличивается вдвое при таком условии:
Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 3
3. Умножить на 4
Программа для исполнителя Калькулятор —это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 60, и при этом траектория вычислений содержит число 16 и не содержит число 21?
Ответ: 40.
Пример 4 с немного необычной командой — возвести в квадрат. Но для нашей программы, оно нипочём.
Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Возвести в квадрат
Программа для исполнителя Калькулятор нипочём это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 38?
Ответ: 266.
Таким образом, разобрав несколько типичных примеров 23 задания, можно сделать вывод, что решения для любого типа — типичное.
Всем удачи, спасибо за внимание! Надеюсь моя статья поможет Вам при подготовке к экзамену.
Автор: #матвей_ч 18 лет, соавтор канала Хакнем Школа, город Москва (Ярославль)