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