Задача к ЕГЭ по информатике на тему «количество результатов выполнения программ» №1

Просмотров 5 Комментарии 0

Исполнитель преобразует число, записанное на экране. У исполнителя есть команды, которым присвоены номера:

1. Прибавить $2$

2. Умножить на $2$ и прибавить $1$

Первая команда увеличивает число на экране на $2,$ вторая — увеличивает число в $2$ раза и добавляет $1.$ Программа для исполнителя — это последовательность команд.

Сколько различных результатов можно получить из исходного числа $6$ после выполнения программы, содержащей ровно $12$ команд?

Решение 1 (Рекурсия)

ans = set()
def f(start, com):
    global ans
    if com == 0:
        ans.add(start)
        return 0
    f(start + 2, com - 1)
    f(start * 2 + 1, com - 1)
f(6, 12)
print(len(ans))

Решение 2 (Динамика)

ans = set()
ans.add(6)
for cnt in range(12):
    can_get = set()
    for i in ans:
        can_get.add(i + 2)
        can_get.add(i * 2 + 1)
    ans = can_get
print(len(ans))

Ответ: 1286