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

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

Исполнитель Калькулятор преобразует число, записанное на экране.
У исполнителя три команды. Каждой команде присвоен номер:
1. Прибавить 1,
2. Прибавить 2,
2. Умножить на 4
Первая из них увеличивает число на экране на $1$ , второе — увеличивает его на $2$ , третья — увеличивает его в $4$ раза.
Программа — это последовательность команд.
Сколько есть программ, которые преобразуют число $2$ в число $17$ ?

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

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 * 4, y)

print(f(2, 17))

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

a = [0] * 100
a[2] = 1
for i in range(3, 18):
    a[i] = a[i - 1] + a[i - 2]
    if i % 4 == 0:
        a[i] += a[i // 4]
print(a[17])

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

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

Если число делится на 4, то вариантов последней команды три: прибавить 1, прибавить 2 и умножить на 4, тогда $R (n) = R (n − 1) + R(n − 2 ) + R (n : 4)$ . Заполним таблицу по данной формуле:

|2-|3-|4--|5-|6-|7-|8--|-9-|10-|11--|12-|13--|-14--|15--|-16-|-17---| |--|--|---|--|--|--|---|---|---|----|---|----|-----|----|----|------| -1--1--2---3--5--8--14--22--36--58---95--153--248---401--651--1052--|

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

Ответ: 1052