23.01 Количество программ из A в B

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

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. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: .

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

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