У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 2.
Первая из них увеличивает на 2 число на экране, вторая удваивает его. Программа для Удвоителя - это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 42?
Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее кратное 2, не превосходящее n. Заметим, что мы можем получить только n, кратные 2.
Верно следующее соотношение: R(n) = R(n / 2) + R(n − 2) (если n > 2).
При n = 4 R(n)) = 2 (один способ: прибавлением двойки, второй способ: умножением на два). Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 42. R(n) для любого нечетного n равно 0.
Имеем:
R(4)= 2,
R(6) = R(3) + R(4) = 0 + 2 = 2,
R(8) = R(4) + R(6) = 2 + 2 = 4,
R(10) = R(5) + R(8) = 0 + 4 = 4,
R(12) = R(6) + R(10) = 2 + 4 = 6,
R(14) = R(7) + R(12) = 0 + 6 = 6,
R(16) = R(8) + R(14) = 4 + 6 = 10,
R(18) = R(9) + R(16) = 0 + 10 = 10,
R(20) = R(10) + R(18) = 4 + 10 = 14.
R(22) = R(11) + R(20) = 0 + 14 = 14.
R(24) = R(12) + R(22) = 6 + 14 = 20.
R(26) = R(13) + R(24) = 0 + 20 = 20.
R(28) = R(14) + R(26) = 6 + 20 = 26.
R(30) = R(15) + R(28) = 0 + 26 = 26.
R(32) = R(16) + R(30) = 10 + 26 = 36.
R(34) = R(17) + R(32) = 0 + 36 = 36.
R(36) = R(18) + R(34) = 10 + 36 = 46.
R(38) = R(19) + R(36) = 0 + 46 = 46.
R(40) = R(20) + R(36) = 14 + 46 = 60.
R(42) = R(21) + R(40) = 0 + 60 = 60.
Ответ: 60.
Приведём другое решение на языке Python.
def f(x, y):
if x == y:
return 1
if x > y:
return 0
return f(x + 2, y) + f(x * 2, y)
print(f(2, 42))