Задание №13 ЕГЭ Информатика с ответом и решением
Ответ: 152
Условие
Исполнитель РазДваТри преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера.
1. Прибавить 1.
2. Умножить на 2.
3. Умножить на 3.
Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья умножает на 3.
Программа для исполнителя РазДваТри — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 40 и при этом траектория вычислений содержит число 12 и не содержит числа 14?
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 3 траектория будет состоять из чисел 9, 10, 20.
Подсказки — как подойти к решению
- Итог — произведение двух счётчиков: программы из старта в обязательное число и из него в цель. Запрещённое число при подсчёте считай недостижимым, иначе ответ завысится.
- Таблицу строй по возрастанию: в каждое n ведут шаги из n−1, из n/2 при чётном n и из n/3 при кратном трём. Обратный ход от цели здесь считать неудобно.
Решение
Искомое количество программ равно количеству программ, получающих из числа 1 число 40. Траектория вычислений не должна содержать числа 14 и должна содержать число 12.
Пусть R(n) — количество программ, которые число 1 преобразуют в число n.
Верно следующее соотношение:
R(n) = R(n – 1) + R(n : 2) (если n чётно) + R(n : 3) (если n кратно 3).
R(1) = 1;
R(2) = 2;
R(3) = 3;
R(4) = 5;
R(5) = 5;
R(6) = 10;
R(7) = 10;
R(8) = 15;
R(9) = 18;
R(10) = 23;
R(11) = 23;
R(12) = 38.
Программ для получения числа 40 из числа 12, не содержащих числа 14, всего 4, их можно перечислить: 121...1, 131, 21...1, 31111.
Таким образом, количество программ, удовлетворяющих условию задачи, равно 38 · 4 = 152.
Ответ: 152.
Приведём другое решение на языке Python.
def f(x, y):
if x > y or x == 14:
return 0
if x == y:
return 1
else:
return f(x + 1, y) + f(x * 2, y) + f(x * 3, y)
print(f(1, 12) * f(12, 40))
Типичные ошибки
- Найден только первый сомножитель. Не забудь отдельно посчитать программы из обязательного числа в цель и перемножить оба значения.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №13 по информатике