Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая увеличивает число в 2 раза.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 1 в число 16?
Решение динамикой
a = [0] * (16 + 1) # Создаем ячейки до конечного числа включительно
a[1] = 1 # Задаём начало в числе 1
for i in range(2, 16 + 1):
a[i] = a[i - 1] # В текущее число можно попасть командой +1
if i % 2 == 0: # Если в текущее число можно было попасть командой *2
a[i] += a[i // 2]
print(a[16])
Решение рекурсией
def f(a):
if a > 16:
return 0
if a == 16:
return 1
return f(a + 1) + f(a * 2)
print(f(1))
Решение руками
В четные числа мы можем попасть из числа деленного на 2 или предыдущего, а в нечетные только из предыдущих.
Получается, что в число 2 мы можем попасть из 1 двумя разными способами.
В число 3 мы можем попасть только из 2.
В число 4 мы можем попасть из 2 или 3.
В число 5 мы можем попасть только из 4.
И т.д.
