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

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

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

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

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

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

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

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

a = [0] * (10 + 1)  # Создаем ячейки до конечного числа включительно
a[1] = 1  # Задаём начало в числе 1
for i in range(2, 10 + 1):
    # В текущее число i можно попасть командой +1 и +2
    a[i] = a[i - 1] + a[i - 2]
print(a[10])

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

# Аргумент a - текущее число, к которому применяются команды
def f(a):
    if a > 10:  # Число стало больше конечного результата, его достигнуть уже не выйдет
        return 0  # Возвращаем 0, не изменяющее количество траекторий
    if a == 10:  # Достигли конечного результата
        return 1  # Возвращаем 0, увеличивающее количество траекторий на 1
    return f(a + 1) + f(a + 2)  # Суммируем количество траекторий от рекурсивных вызовов


print(f(1)) # Запускаем функцию от исходного числа 1

Ответ: 55