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

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

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

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

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

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

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $121$ при исходном числе $1$ траектория будет состоять из чисел $2,4,5.$

Решение рекурсией:

def f(a, b):
    if a > b:
        return 0
    if a == b:
        return 1
    return f(a + 1, b) + f(a + 2, b)

print(f(1, 10))

Решение динамикой:

a = [0] * 1000
a[1] = 1
for i in range(10):
    a[i+1] += a[i]
    a[i+2] += a[i]
print(a[10])

Ответ: 55