Задача к ЕГЭ по информатике на тему «количество программ из a в b где траектория вычислений не содержит число(-а)» №1

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

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

Прибавить $1$ ;
Сделай нечётное.

Выполняя первую команду, исполнитель увеличивает число на $1$ , а выполняя вторую — из числа $k$ получает число $2k + 1$ .

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

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

def f(s, fi):
    if s > fi:
        return 0
    if s == 21:
        return 0
    if s == fi:
        return 1
    return f(s + 1, fi) + f(s * 2 + 1, fi)
print(f(1, 25))

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

a = [0] * 26
a[1] = 1
for i in range(2, 26):
    a[i] += a[i - 1]
    if i % 2 != 0:
        a[i] += a[i // 2]
    if i == 21:
        a[i] = 0
print(a[25])

Ответ: 20