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

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

Исполнитель ХЛЕБУШЕК преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 1,
2. Прибавь 2,
3. Прибавь 3.
Первая из них увеличивает число на экране на 1, вторая — увеличивает его на 2, третья — увеличивает его на 3.
Программа для ХЛЕБУШКа — это последовательность команд.
Сколько есть программ, которые преобразуют число 1 в число 14?

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

def f(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    return f(x + 1, y) + f(x + 2, y) + f(x + 3, y)

print(f(1, 14))

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

a = [0] * 100
a[1] = 1
for i in range(2, 15):
    a[i] = a[i - 1] + a[i - 2] + a[i - 3]
print(a[14])

Решение аналитикой:

Количество программ, которые преобразуют число 1 в число n, обозначим $R (n).$ Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, $R (1) = 1.$ Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда $R (2) = 1.$ Число “3” можем получить из чисел 1 и 2 — $R (3) = R(1) + R (2) = 2.$ Число “4” получаем из 1, 2 и 3 — $R (4) = R (1 ) + R (2) + R(3) = 6.$ Заметим, что количество программ для получения числа n находится по формуле — $R (n) = R(n − 3 ) + R (n − 2) + R(n − 1 ).$ Составим таблицу по данной формуле:

|--|--|--|--|--|----|---|---|---|-----|----|----|-----|-----| |1-|2-|3-|4-|5-|-6--|7--|8--|-9-|-10--|11--|-12-|-13--|-14--| |1 |1 |2 |4 |7 |13 |24 |44 |81 |149 |274 |504 |927 |1705 | -------------------------------------------------------------

Отсюда получаем искомое количество программ — 1705.

Получается ответ: $1705.$

Ответ: 1705