Задание №13 ЕГЭ Информатика с ответом и решением
Ответ: 13
Условие
Исполнитель РазДва преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1.
2. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя РазДва — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 2 в число 24 и при этом траектория вычислений содержит ровно одно из чисел 11 и 12?
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 4 траектория будет состоять из чисел 8, 9, 18.
Подсказки — как подойти к решению
- Фраза «ровно одно из чисел» означает два непересекающихся случая: маршрут проходит через первое число и обходит второе, либо наоборот. Посчитай каждый случай отдельно и сложи.
- В каждом случае перемножь счётчики до обязательной точки и после неё, но запрещённое число выкалывает часть путей — ищи обходные варианты, например через умножение.
Решение
Искомое количество программ равно количеству программ, получающих из числа 2 число 24. Траектория вычислений не должна содержать число либо число 11, либо число 12.
Пусть R(n) — количество программ, которые число 2 преобразуют в число n.
Верно следующее соотношение:
R(n) = R(n – 1) + R(n : 2) (если n чётно).
Найдём количество программ, преобразующих число 2 в число 24, траектория вычислений должна содержать число 11, но не содержать число 12:
R(2) = 1;
R(3) = 1;
R(4) = 2;
R(5) = 2;
R(6) = 3;
R(7) = 3;
R(8) = 5;
R(9) = 5;
R(10) = 7;
R(11) = 7.
Из числа 11 число 24 можно получить только последовательностью команд 211, поскольку траектория не должна содержать число 12.
Найдём количество программ, преобразующих число 2 в число 24, траектория вычислений должна содержать число 12, но не содержать число 11:
R(2) = 1;
R(3) = 1;
R(4) = 2;
R(5) = 2;
R(6) = 3.
Из числа 6 число 24 можно получить либо последовательностью команд 22, либо последовательностью команд 21..1, поскольку траектория не должна содержать число 11. Значит, всего команд 3 · 2 = 6.
Таким образом, ответ — 7 + 6 = 13.
Ответ: 13.
Приведём другое решение Лапташкина Виталия на языке Python.
def ab1(s, f):
if s > f or s == 12:
return 0
elif s == f:
return 1
else:
return ab1(s+1, f) + ab1(s*2, f)
def ab2(s, f):
if s > f or s == 11:
return 0
elif s == f:
return 1
else:
return ab2(s+1, f) + ab2(s*2, f)
print(ab2(2, 12) * ab2(12, 24)+(ab1(2, 11) * ab1(11, 24)))
Приведём решение Юрия Красильникова на языке Python.
def ways(start,end,z): # z - список чисел, которые нельзя получать в процессе
if start > end or start in z: return 0
if start == end: return 1
return ways(start+1,end,z)+ways(start*2,end,z)
print(ways(2,11,[12])*ways(11,24,[12]) + ways(2,12,[11])*ways(12,24,[11]))
# список даёт возможность задавать несколько «запретных» чисел - или ни одного.
Типичные ошибки
- Посчитан только один из двух случаев. Союз «ровно одно из чисел» требует отдельно сложить варианты с каждой обязательной точкой, иначе часть программ теряется.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №13 по информатике