Задание №13 ЕГЭ Информатика с ответом и решением
Ответ: 200
Условие
Исполнитель Аллегро преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера.
1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 3.
Первая команда увеличивает число на экране на 1, вторая увеличивает число на
2, третья умножает его на 3. Программа для исполнителя Аллегро — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 18 и при этом траектория вычислений содержит число 8, но не содержит число 13?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.
Подсказки — как подойти к решению
- Маршрут обязан пройти через обязательное число, поэтому считай отдельно программы из 3 в 8 и из 8 в 18, а затем перемножь. Запрещённое число при подсчёте игнорируй полностью.
- Удобно рисовать граф: в вершину n ведут стрелки из n−1, из n−2 и, если n делится на три, из n/3. Ставь у вершины количество путей, а не сами пути.
Решение
Нужно найти количество программ, которые из 3 получают 8, количество программ, которые из 8 получают 18, но не проходит через 13 и перемножить найденные значения. Сначала найдём количество программ, получающих 8 из 3.
Приведём решение на языке 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(3, 8) * f(8, 18))
Ответ: 200.
Приведём решение Евгения Джобса (графическое).
Изобразим в виде графа, как можно прийти в определенные числа. И посчитаем количество вычислительных стратегий до каждой вершины из начальной.
Типичные ошибки
- Посчитана лишь первая часть маршрута. Из обязательного числа в конечное тоже ведут программы, и их количество нужно перемножить с уже найденным.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №13 по информатике