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