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