Задание №6526.
Анализ хода исполнения алгоритма. ЕГЭ по информатике
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3 Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 19 результатом является 2, при этом траектория вычислений не содержит числа 7 и содержит 13?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы
СBА при исходном числе 22 траектория состоит из чисел 7, 3, 2.
Пояснение:
Решим задание, написав программу на языке программирования Python.
memo = {}
def count_paths(x, has13=False):
if (x, has13) in memo:
return memo[(x, has13)]
if x == 7 or x < 2:
return 0
if x == 2:
return 1 if has13 else 0
if x == 13:
has13 = True
total = 0
for nx in [x-1, x-4, x//3]:
total += count_paths(nx, has13)
memo[(x, has13)] = total
return total
print(count_paths(19, False)) |
Таким образом, существует
68 программ, для которых при исходном числе 19 результатом является 2, при этом траектория вычислений не содержит числа 7 и содержит 13.
Показать ответ
68
Источник: Демонстрационный вариант ЕГЭ — 2026
Сообщить об ошибке
Тест с похожими заданиями